# Words and Automata

Leader: Juhani Karhumäki

The focus of this group is in **combinatorics on words**
and **automata with applications and decidability** questions.

## Combinatorics on words

This is a fascinating young research area connected to automata, codes, DNA sequencing, crystallography, many areas of algebra, dynamical systems etc. It is an essential tool in problems of pattern matching and string algorithms.

This topic is closely related to research done by the FiDiPro team.

The history of combinatorics of words goes back to the beginning of the 20th century when Axel Thue studied nonrepetitive sequences of symbols. After the publication of Lothaire's book in 1983 the field has developed systematically and rapidly.

In the latest classification of Math. Reviews Combinatorics on Words
is the section **68R15**.

The basic resources for the topic are the books of Lothaire:

- M. Lothaire: Combinatorics on Words. Addison-Wesley, 1983.
- M. Lothaire: Algebraic Combinatorics on Words. Cambridge University Press, 2002.
- M. Lothaire: Applied Combinatorics on Words. Cambridge University Press, 2005.
- C. Choffrut and J. Karhumäki: Combinatorics of Words. In: Handbook of Formal Languages, Vol. 1, 329-438. Springer-Verlag, 1997.

## Automata and Decidability

Automata theory constitutes a cornerstone of the theoretical computer science. Its origins and applications are in switching circuits, natural languages, modelling biological phenomena, programming languages and computability. The latest applications of the automata and formal languages are e.g. in algebra and computer graphics. Decidability questions are concerned with the existence of algorithms for solving problems. The existence of undecidable problems can be seen to pose limitations to the effectiveness of problem solving in mathematics.

- V. Halava, T. Harju, J. Karhumäki: Undecidability Through Post Correspondence Problem, Springer-Verlag, forthcoming monograph.