Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Square-Free Words over Partially Commutative Alphabets
verfasst von : Łukasz Mikulski, Marcin Piątkowski, Wojciech Rytter
Erschienen in: Language and Automata Theory and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
There exist many constructions of infinite words over three-letter alphabet avoiding squares. However, the characterization of the lexicographically minimal square-free word is an open problem. Efficient construction of this word is not known. We show that the situation changes when some letters commute with each other. We give two characterizations (morphic and recursive) of the lexicographically minimal square-free word
$$\widetilde{\mathbf {v}}$$
in the case of a partially commutative alphabet
$$\Theta $$
of size three. We consider the only non-trivial relation of partial commutativity, for which
$$\widetilde{\mathbf {v}}$$
exists: there are two commuting letters, while the third one is blocking (does not commute at all). We also show that the
$$n$$
-th letter of
$$\widetilde{\mathbf {v}}$$
can be computed in time logarithmic with respect to
$$n$$
.