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

- T. Harju and J. Karhumäki,

The equivalence problem of multitape finite automata

Theoret. Comput. Sci.78 (1991), 347 - 355.D0L-equivalence problemwas 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:A strong decidability result is proven for the generalized Post Correspondence Problem in

- T. Harju and J. Karhumäki, Morphisms

Handbook of Formal Languages, Vol 1., Springer-Verlag, 1997, pp. 439 - 510.The PCP is a basic tool for

- V. Halava, T. Harju and M. Hirvensalo

Generalized Post Correspondence Problem for marked morphism

Internat. J. Algebra Comput.10 (2000), 757 - 772.doi:10.1142/S0218196700000376Decision 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

- J. Cassaigne, T. Harju and J. Karhumäki

On the decidability of the freeness of matrix semigroupsInternat. J of Algebra and Comput.,9 (1999), 295 - 305.

- V. Halava and T. Harju

Mortality in matrix semigroups

Amer. Math. Monthly108 (2001), 649 - 653.

(4) Skolem's Problemis one of the long standing open decision problems: Given a linear recurrence equation x_{k}of length n, does it have a zero, x_{k}=0 for some k?The problem was shown to be decidable for lengths at most 5 in

- V. Halava, T. Harju, M. Hirvensalo and J. Karhumäki

Skolem's Problem - On the Border Between Decidability and Undecidability pdf file:

submitted.This problem has an equivalent formulation for powers of matrices.