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. T. Harju and J. Karhumäki, The equivalence problem of multitape finite automata Theoret. Comput. Sci. 78 (1991), 347 - 355. 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 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 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/S0218196700000376 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 J. Cassaigne, T. Harju and J. Karhumäki On the decidability of the freeness of matrix semigroups Internat. J of Algebra and Comput., 9 (1999), 295 - 305. V. Halava and T. Harju Mortality in matrix semigroups Amer. Math. Monthly 108 (2001), 649 - 653. (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 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.