Word Equations and Related Topics. Independence, Decidability and Characterizations
Pysyvä osoite
Verkkojulkaisu
DOI
Tiivistelmä
The three main topics of this work are independent systems and chains of
word equations, parametric solutions of word equations on three unknowns,
and unique decipherability in the monoid of regular languages.
The most important result about independent systems is a new method
giving an upper bound for their sizes in the case of three unknowns. The
bound depends on the length of the shortest equation. This result has
generalizations for decreasing chains and for more than three unknowns.
The method also leads to shorter proofs and generalizations of some old
results.
Hmelevksii’s theorem states that every word equation on three unknowns
has a parametric solution. We give a significantly simplified proof for this
theorem. As a new result we estimate the lengths of parametric solutions
and get a bound for the length of the minimal nontrivial solution and for
the complexity of deciding whether such a solution exists.
The unique decipherability problem asks whether given elements of some
monoid form a code, that is, whether they satisfy a nontrivial equation. We
give characterizations for when a collection of unary regular languages is a
code. We also prove that it is undecidable whether a collection of binary
regular languages is a code.
Kuvaus
Siirretty Doriasta
Sarja
TUCS Dissertations|145
Saavutettavuusominaisuudet
Ei tietoa saavutettavuudesta