• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Local Squares, Periodicity and Finite Automata

Mari Huova, Juhani Karhumäki, Aleksi Saarela, Kalle Saari, Local Squares, Periodicity and Finite Automata. In: Cristian Calude, Grzegorz Rozenberg, Arto Salomaa (Eds.), Rainbow of Computer Science, Lecture Notes in Computer Science 6570, 90–101, Springer, 2011.

http://dx.doi.org/10.1007/978-3-642-19391-0_7

Abstract:

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.

BibTeX entry:

@INBOOK{cHuKaSaSa11a,
  title = {Local Squares, Periodicity and Finite Automata},
  booktitle = {Rainbow of Computer Science},
  author = {Huova, Mari and Karhumäki, Juhani and Saarela, Aleksi and Saari, Kalle},
  volume = {6570},
  series = {Lecture Notes in Computer Science},
  editor = {Calude, Cristian and Rozenberg, Grzegorz and Salomaa, Arto},
  publisher = {Springer},
  pages = {90–101},
  year = {2011},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication