Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
equality languages; dual Post correspondence problem; periodicity forcing
equality languages; dual Post correspondence problem; periodicity forcing
Summary:
Deciding whether a given word is an equality word of two nonperiodic morphisms is also known as the dual Post correspondence problem. Although the problem is decidable, there is no practical decision algorithm. Already in the binary case, the classification is a large project dating back to 1980s. In this paper we give a full classification of binary equality words in which one of the letters has two occurrences.
References:
[1] Barbin-Le R. E., Le Rest M.: Sur la combinatoire des codes à deux mots. Theoret. Comput. Sci. 41 (1985), no. 1, 61–80 (French. English summary). DOI 10.1016/0304-3975(85)90060-X | MR 0841023
[2] Baumslag G.: Topics in Combinatorial Group Theory. Lectures in Mathematics ETH Zürich, Birkhäuser, Basel, 1993. MR 1243634
[3] Culik K. II, Karhumäki J.: On the equality sets for homomorphisms on free monoids with two generators. RAIRO Inform. Théor. 14 (1980), no. 4, 349–369. DOI 10.1051/ita/1980140403491 | MR 0607436
[4] Day J. D., Reidenbach D., Schneider J. C.: On the dual post correspondence problem. Internat. J. Found. Comput. Sci. 25 (2014), no. 8, 1033–1048. MR 3315805
[5] Day J. D., Reidenbach D., Schneider J. C.: Periodicity forcing words. Theoret. Comput. Sci. 601 (2015), 2–14. DOI 10.1016/j.tcs.2015.08.033 | MR 3396330
[6] Ehrenfeucht A., Karhumäki J., Rozenberg G.: The (generalized) Post correspondence problem with lists consisting of two words is decidable. Theoret. Comput. Sci. 21 (1982), no. 2, 119–144. DOI 10.1016/0304-3975(89)90080-7 | MR 0677104
[7] Ehrenfeucht A., Karhumäki J., Rozenberg G.: On binary equality sets and a solution to the test set conjecture in the binary case. J. Algebra 85 (1983), no. 1, 76–85. DOI 10.1016/0021-8693(83)90119-9 | MR 0723068
[8] Hadravová J.: Structure of Equality Sets. PhD. Thesis, Charles University in Prague, Praha, 2015.
[9] Hadravová J., Holub Š.: Equation $x^iy^jx^k=u^iv^ju^k$ in words. Language and Automata Theory and Applications, Lecture Notes in Comput. Sci., Springer, Cham, 2015, pp. 414–423. MR 3344820
[10] Halava V., Harju T., Hirvensalo M.: Binary (generalized) Post correspondence problem. Theoret. Comput. Sci. 276 (2002), no. 1–2, 183–204. DOI 10.1016/S0304-3975(01)00157-8 | MR 1896352
[11] Halava V., Holub Š.: Binary (Generalized) Post Correspondence Problem is in $P$. TUCS Technical Report, 785, Turku, 2006. MR 2081369
[12] Holub Š.: A unique structure of two-generated binary equality sets. Developments in Language Theory (Ito M., ed.), 6th International Conf., Kyoto, 2002, Lecture Notes in Comput. Sci., 2450, Springer, Berlin, 2003, pp. 245–257. MR 2177348 | Zbl 1015.68089
[13] Holub Š.: Binary equality sets are generated by two words. J. Algebra 259 (2003), no. 1, 1–42. DOI 10.1016/S0021-8693(02)00534-3 | MR 1953706 | Zbl 1010.68101
[14] Holub Š.: Binary equality languages for periodic morphisms. Algebraic Systems, Formal Languages and Conventional and Unconventional Computation Theory, RIMS Kokyuroku, 1366, Kyoto University, 2004, pp. 1880–2818.
[15] Karhumäki J., Maňuch J., Plandowski W.: On defect effect of bi-infinite words. Mathematical Foundations of Computer Science, 1998 (Brno), Lecture Notes in Comput. Sci., 1450, Springer, Berlin, 1998, pp. 674–682. MR 1684115
[16] Lothaire M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, 90, Cambridge University Press, Cambridge, 2002.
[17] Lyndon R. C., Schützenberger, M. P.: The equation $a^M=b^Nc^P$ in a free group. Michigan Math. J. 9 (1962), no. 4, 289–298. DOI 10.1307/mmj/1028998766 | MR 0162838
[18] Maňuch J.: Defect Theorems and Infinite Words. TUCS Dissertations, 41, Turku, 2002.
[19] Post E. L.: A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc. 52 (1946), no. 4, 264–268. DOI 10.1090/S0002-9904-1946-08555-9 | MR 0015343 | Zbl 0063.06329
[20] Rozenberg G., Salomaa A., eds.: Handbook of Formal Languages, Vol. 1: Word, Language, Grammar. Springer, New York, 1997. MR 1469993
[21] Spehner J.-C.: Quelques problèmes d'extension, de conjugaison et de presentation des sous-monoïdes d'un monoïde libre. Thèse, Université Paris VII, Paris, 1976 (French).
Search
Partner of
