Words and Automata
– Automata Theory

Applications of finite automata

Automata theory has been a traditional research topic of the group. We believe that we have achieved a few lasting results in that area. Most notably, the multiplicity problem of finite automata was considered as one of the most important open problems for 30 years until it was solved by algebraic methods in

• T. Harju and J. Karhumäki: The equivalence problem of multitape finite automata. Theoretical Computer Science 78 (1991) 347-355.

The current main focus is on new features of the theory. It is undeniable that automata theory has experienced a remarkable revival over the last 15 years. This is mainly due to its connections to other areas like model checking, novel models of computing, and image manipulation.

• J. Karhumäki and J. Kari: Finite Automata, Image Manipulation and Automatic Real Functions, a chapter in Handbook of Automata, European Mathematical Society (to appear).

- Finite automata are used in proving an amazing improved solution for the existence of aperiodic tilings of the plane:

• J. Kari: A small aperiodic set of Wang tiles. Discrete Math. 160 (1996) 259-264.

- Algebra is another topic where finite automata are useful. The solution of the decidability of isomorphism problem for finitely generated subsemigroups of free semigroups is a nice example of such an application.

• C. Choffrut, T. Harju and J. Karhumäki: A note on decidability questions on presentations of word semigroups. Theoret. Comput. Sci. 183 (1997) 83-92.

Another recent survey is

• T. Harju and J. Karhumäki: Finite transducers and rational transduction, a chapter in Handbook of Automata, European Mathematical Society (to appear)

Decidability questions

Algorithmic decision problems are central in theoretical computer science. In particular, we are interested in simply formulated problems that lie on the borderline between decidable and undecidable problems.

- Surprisingly even very simple substitutions provide undecidability: It is undecidable whether two substitutions agree on the language ab^*c, see

• J. Karhumäki and L. P. Lisovik: The equivalence problem for finite substitutions on ab^*c, with applications. Intern. J. Found. Comput. Sci. 14 (2003) 699-710.

- One challenging open problem is to decide whether a given finitely generated semigroup of 2-by-2 integer matrices is free. The importance of the problem comes from the fact that such matrix semigroups are natural extensions of word semigroups.

• J. Cassaigne, T. Harju, and J. Karhumäki: On the undecidability of freeness of matrix semigroups. Intern. J. Alg. & Comp. 9 (1999) 295-305.

- Also, the Skolem's problem for integer matrices is still open: Given an n-by-n integer matrix M, does there exist a power p such that the right upper-corner of M^p is zero?

• V. Halava, T. Harju, M. Hirvesalo, and J. Karhumäki: Skolem's Problem - On the Border Between Decidability and Undecidability. Submitted.

Post Correspondence Problem: This problem is the oldest purely combinatorial undecidable problem. The instances of the problem are pairs (g,h) of morphisms of word and the problem asks for the existence of a solution word w for which g(w)=h(w). There are many variants of this problem that turn out to be decidable.

- The binary Post Correspondence Problem was shown to be decidable in

• A. Ehrenfeucht, J. Karhumäki and G. Rozenberg: The (generalized) Post correspondence problem with lists consisting of two words is decidable. Theoret. Comput. Sci. 21 (1982) 119-144.

See also

• V. Halava, S. Holub: Binary (generalized) Post Correspondence Problem is in P. Submitted.

More recently, the solution was extended to all marked morphisms.

• V. Halava, M. Hirvensalo and R. de Wolf: Marked PCP is decidable. Theoret. Comput. Sci. 255 (2001) 193-204.

The problem area is surveyed in

• T. Harju and J. Karhumäki: Morphisms. In: Handbook of Formal Languages, 439-510, Springer-Verlag, 1997.