Fundamentals of Computing and Discrete Mathematics

Words and Automata
– Combinatorics on Words

Periodicity and repetitions in words

Research on combinatorics on words has revealed a number of fundamental mathematical results such as the Periodicity Lemma of Fine and Wilf characterizing how long two periodic events have to match in order to have a common period.

- On infinite words a fundamental question is when does local regularity imply global regularity. Results on this question can be seen giving borderlines between predictable and chaotic behaviour. One of our main contributions describes the exact borderline where global regularity means that the word is ultimately periodic and local regularity means certain type of repetition at the end of the prefixes.

  • J. Karhumäki, A. Lepistö and W. Plandowski: Locally periodic infinite words and a chaotic behaviour. J. Comb. Theor., Ser. A 100 (2002) 250-264.
  • A. Lepistö: On Relations between Local and Global Periodicity, Ph.D. Thesis, University of Turku, TUCS Dissertations 43, 2002.
  • K. Saari: On the Frequency and Periodicity of Infinite Words, Ph.D. Thesis, University of Turku, TUCS Dissertations 97, 2008.

- The exact order of repetition in binary words which allow exponentially many words of length n is determined in

- A Duval extension of an unbordered word w of length n is a word wu which does not have unbordered factors of length greater n. The following paper proves the 20 year old Duval's Conjecture:

Let w be a word of length n. Then the length of a nontrivial Duval's extension wu of w satisfies |wu| < 2n-1.

Equations on words

Algorithmic solvability of word equations by G. S. Makanin is one of the fundamental achievements of mathematics in recent decades. Advances on the complexity of this problem have been made recently by W. Plandowski, who is a regular visitor of our group.

- Systems of equations is a classical topic in commutative algebra. In combinatorics on words this topic is motivated by Ehrenfeucht's Conjecture (from early 1970's) which was solved by Albert and Lawrence (1985), and Guba (1986). The theorem is a noncommutative version of Hilbert's basis theorem.
Ehrenfeucht's Compactness Theorem:

Every system of word equations has a finite equivalent subsystem.

Surveys of the topic are given in

  • T. Harju, J. Karhumäki and W. Plandowski: Independent Systems of Equations. Chapter 13 in M. Lothaire, Algebraic Combinatorics on Words Cambridge University Press, 2002.
  • T. Harju and D. Nowotka: On the independence of equations in three variables. Theoret. Comput. Sci. 307: 139-172, 2003.
  • E. Czeizler: Intricacies of Words Equations, Ph.D. Thesis, University of Turku, TUCS Dissertations 88, 2007.

Elegant and more algebraic proof methods for these problems were established in

  • A. Saarela: Word Equations and Related Topics: Independence, Decidability and Characterizations, Ph. D. Thesis, TUCS Dissertations 145, 2012.

- First criteria were introduced which allow proving that some languages are not expressible as solutions of word equations, see

- Related to this topic is the theory of language equations. M. Kunc (post doc in Turku in 2005) solved the famous 30-year-old Conway's Problem on commutation of language.

  • C. Choffrut, J. Karhumäki, and N. Ollinger: The commutation of finite sets: a challenging problem. Theoret. Comput. Sci. 273: 69-79, 2002.

- The Defect Theorem formulates a weak dimension property of words. In the weak form the theorem can be stated as follows:

If n words satisfies a nontrivial relation, then these words can be expressed using n-1 simpler words.

One of the basic articles on this topic is the following:

  • T. Harju and J. Karhumäki: Many aspects of the defect effect. Theoret. Comput. Sci. 324(1): 35-54, 2004.
Last modified: Tuesday October 07, 2014