Advertisement
Published in:
2011 | OriginalPaper | Chapter
Local Squares, Periodicity and Finite Automata
Authors : Mari Huova, Juhani Karhumäki, Aleksi Saarela, Kalle Saari
Published in: Rainbow of Computer Science
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.