Undecidability in w-Regular Languages

• Autorzy: Halava V. , Harju T. , Karhumäki J.
• Języki publikacji: EN

Abstrakty

EN

In the infinite Post Correspondence Problem an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word a such that h(a) = g(a). In the general case this problem was shown to be undecidable by K. Ruohonen (1985). Recently, it was proved that the infinite PCP is undecidable already when the domain alphabet of the morphisms consists of at least 9 letters. Here we show that the problem is undecidable for instances where the morphisms have a domain of 6 letters, when we restrict to solutions of w-languages of the form Rw where R is a given regular language.

Słowa kluczowe

EN

Post Correspondence Problem; infinite words; semi-Thue system; regular language; undecidability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 119--125
• Opis fizyczny: bibliogr. 14 poz.

Twórcy

autor

Halava V.

autor

Harju T.

autor

Karhumäki J.

• Department of Mathematics, University of Turku, FIN-20014 Turku, Finland M.Steinby Turku, Finland,,

Bibliografia

• [1] V.D. Blondel, V. Canterini: Undecidable problems for probabilistic automata of fixed dimension. Theory Comput. Syst., 36, 3 (2003), 231-245.
• [2] C. Choffrut, J. Karhumäki: Test sets for morphisims with bounded delay. Discrete Appl. Math., 12 (1985), 93-101.
• [3] V. Claus. Some remarks on PCP(k) and related problems. Bull. EATCS, 12 (1980), 54-61.
• [4] A. Ehrenfeucht, J. Karhumäki, G. Rozenberg: The (generalized) Post Correspondence Problem with lists consisting of two words is decidable. Theoret. Comput. Sci., 21 (1982), 119-144.
• [5] V. Halava, T. Harju: Infinite solutions of the marked Post Correspondence Problem. In J. Karhumäki, W. Brauer, H. Ehrig, A. Salomaa, Eds., Formal and Natural Computing, volume 2300 of Lecture Notes in Comput. Sci., pp 57-68. Springer, Berlin, 2002.
• [6] V. Halava, T. Harju: Infinite Post Correspondence is Undecidable for Instance of Size 9. To appear in Theor. Inform. Appl., also as TUCS Tech. Report 662, 2005.
• [7] V. Halava, T. Harju, M. Hirvensalo: Binary (generalized) Post Correspondence Problem. Theoret. Comput. Sci., 276 (2002), 183-204.
• [8] V. Halava, T. Harju, J. Karhumäki: Decidability of the binary infinite Post Correspondence Problem. Discrete Appl. Math., 130 (2003), 521-526.
• [9] V. Halava, T. Harju, J. Karhumäki, M. Latteux: Post Correspondence Problem for morphisms with unique blocks. In (S. Brlek, C. Reutenauer, eds) Words 2005, Publication du LaCIM 36(2005), 265-275.
• [10] T. Harju, J. Karhumäki: Morphisms. In G. Rozenberg, A. Salomaa, Eds., Handbook of Formal Languages, volume 1. pp. 439-510, Springer, Berlin, 1997.
• [11] Y.Matiyasevich, G. Sénizergues: Decision problems for semi-Thue systems with a few rules. Theor. Comput. Sci. 330, 1 (2005), 145-169.
• [12] E. Post: A variant of a recursively unsolvable problem. Bull. of Amer. Math. Soc., 52 (1946), 264-268.
• [13] K. Ruohonen: Reversible machines and Post's correspondence problem for biprefix morphisms. Elektron. Informationsverarb. Kybernet. (EIK), 21, 12 (1985), 579-595.
• [14] A. Salomaa: Formal Languages. Academic Press, New York, 1973.