To Homepage of Tero Harju

Topics in

Automata and Decidability


In the theory of automata one studies mathematical foundations of computer science. This theory considers nowadays not only the classical models of computability (such as finite automata and Turing machines), but also increasingly the more recent models of computability, such as genetic algorithms (DNA-computing) and quantum computing. These new areas require new techniques that come from different mathematical areas.

*Topics*

(1) Undecidability: My contribution to computability is mostly in the study of the boundaries between decidable and undecidable problems that concern automata, semigroups, and combinatorial aspects of words.

My main contributions to this topic solved a 30 years old famous problem on finite automata with multiplicities (i.e., rational formal power series). The main argument of the proof uses an embedding result for ordered groups into division rings. The recent book by J. Sakarovitch devotes a chapter to this solution.

The famous D0L-equivalence problem was generalized to infinite words in
  • K. Culik and T. Harju,
    The omega-sequence problem for DOL systems is decidable,
    J. Assoc. Comput. Mach. 31 (1984), 282 - 298.

(2) Post Correspondence Problem (PCP) (due to Emil Post, 1946) was the first purely combinatorial problem that was shown to be undecidable. This result also merged algebraic homomorphisms to computability. A survey on morphisms in computability and combinatorics of words including many aspects of the PCP given in the handbook article:

  • T. Harju and J. Karhumäki, Morphisms pdf
    Handbook of Formal Languages, Vol 1., Springer-Verlag, 1997, pp. 439 - 510.
A strong decidability result is proven for the generalized Post Correspondence Problem in The PCP is a basic tool for

Decision questions for semigroup presentations are considered in \cite{CHK} (with C. Choffrut and J. Karhum\"aki).

The article \cite{EHR3} (with A. Ehrenfeucht and G. Rozenberg) gives a characterization of transitivity of finite permutable semigroups.

(3) Decision Problems for Matrices: Already small integer matrices provide simple undecidable instances. Indeed, as was shown by Paterson in 1970, it is undecidable whether the null matrix can be generated from a finite set of 3-by-3 integer matrices; see the above handbook article "Morphisms". For other problems, see

(4) Skolem's Problem is one of the long standing open decision problems: Given a linear recurrence equation xk of length n, does it have a zero, xk=0 for some k?

The problem was shown to be decidable for lengths at most 5 in

This problem has an equivalent formulation for powers of matrices.

To Homepage of Tero Harju