On the Decidability of Some Problems Concerning Morphisms, Regular Sets, and Post Correspondence Problem

Article type: Research Article

Authors: Turakainen, Paavo

Affiliations: Department of Mathematical Sciences, University of Oulu, PO Box 3000 OULU, 90401 Finland Paavo. [email protected]

Note: [] Address for correspondence: Department of Mathematical Sciences, University of Oulu, PO Box 3000 OULU, 90401 Finland

Abstract: Regular languages are divided into equivalence classes according to the lengths of the words and both the universal and the existential equivalence of rational transductions on the set of these classes is studied. It is shown that the cardinality equivalence problem is undecidable for ϵ-free finite substitutions. The morphic replication equivalence problem is arithmetized and an application to word equations is presented. Finally, the generalized Post correspondence problem is modified by using a single inverse morphism or a single finite substitution or its inverse instead of two morphisms.

Keywords: Decidability, equivalence, morphism, morphic replication, finite substitution, word equation

DOI: 10.3233/FI-1999-381217

Journal: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 209-221, 1999