On the decidability of some problems concerning morphisms, regular sets, and post correspondence problem

• Autorzy: Turakainen P.
• Języki publikacji: EN

Abstrakty

EN

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 e-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.

Słowa kluczowe

EN

decidability; equivalence; morphism; morphic replication; finite substitution

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1999
• Tom: Vol. 38, Nr 1,2
• Strony: 209--221
• Opis fizyczny: bibliogr. 18 poz.

Twórcy

autor

Turakainen P.

• Department of Mathematical Sciences, University of Oulu, PO Box 3000 Oulu, 90401 Finland,