Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Local Squares, Periodicity and Finite Automata
verfasst von : Mari Huova, Juhani Karhumäki, Aleksi Saarela, Kalle Saari
Erschienen in: Rainbow of Computer Science
Verlag: Springer Berlin Heidelberg
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
We consider the general problem when local regularity implies the global one in the setting where local regularity means the existence of a square of certain length in every position of an infinite word. The square can occur as centered or to the left or to the right from each position. In each case there are three variants of the problem depending on whether the square is that of words, that of abelian words or, as an in between case, that of so called
k
-abelian words. The above nine variants of the problem are completely solved, and some open problems are addressed in the
k
-abelian case. Finally, an amazing unavoidability result for 2-abelian squares is obtained.