Binary equality words with two \(b\)’s. (English) Zbl 1463.68044

A word \(w\) satisfying \(g(w)=h(w)\) for two morphisms \(g\) and \(h\) is called an equality word of the morphisms. The dual Post correspondence problem consists in deciding if, for a given word \(w\), two nonperiodic morphisms \(g\) and \(h\) with this property exist. The problem is decidable but there is no practical decision algorithm. The authors give a full classification of binary equality words in which one of the letters has two occurrences: they are of the form \(a^n b^2\), \(b^2 a^n\), \(b a^n b\), \(a^{n+1} b^2 a^n\), \(a^n b^2 a^{n+1}\), \(a^n b a b a^n\), \(a^n b b a^n\) or \(a^n b a^{n+m} b a^m\).


68R15 Combinatorics on words
Full Text: DOI


[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) · Zbl 0593.20066 · doi:10.1016/0304-3975(85)90060-X
[2] Baumslag G., Topics in Combinatorial Group Theory, Lectures in Mathematics ETH Zürich, Birkhäuser, Basel, 1993 · Zbl 0797.20001
[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 · Zbl 0454.20048 · doi:10.1051/ita/1980140403491
[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 · Zbl 1317.68127
[5] Day J. D.; Reidenbach D.; Schneider J. C., Periodicity forcing words, Theoret. Comput. Sci. 601 (2015), 2-14 · Zbl 1329.68195 · doi:10.1016/j.tcs.2015.08.033
[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 · Zbl 0493.68076 · doi:10.1016/0304-3975(89)90080-7
[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 · Zbl 0523.68066 · doi:10.1016/0021-8693(83)90119-9
[8] Hadravová J., Structure of Equality Sets, PhD. Thesis, Charles University in Prague, Praha, 2015 · Zbl 1240.68162
[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 · Zbl 1451.68217
[10] Halava V.; Harju T.; Hirvensalo M., Binary (generalized) Post correspondence problem, Theoret. Comput. Sci. 276 (2002), no. 1-2, 183-204 · Zbl 1023.03038 · doi:10.1016/S0304-3975(01)00157-8
[11] Halava V.; Holub Š., Binary (Generalized) Post Correspondence Problem is in \(P\), TUCS Technical Report, 785, Turku, 2006
[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 · Zbl 1015.68089
[13] Holub Š., Binary equality sets are generated by two words, J. Algebra 259 (2003), no. 1, 1-42 · Zbl 1010.68101 · doi:10.1016/S0021-8693(02)00534-3
[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 · Zbl 0914.68154
[16] Lothaire M., Algebraic Combinatorics on Words, Encyclopedia of Mathematics and Its Applications, 90, Cambridge University Press, Cambridge, 2002 · Zbl 1001.68093
[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 · Zbl 0106.02204 · doi:10.1307/mmj/1028998766
[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 · Zbl 0063.06329 · doi:10.1090/S0002-9904-1946-08555-9
[20] Rozenberg G.; Salomaa A.; eds., Handbook of Formal Languages, Vol. 1: Word, Language, Grammar, Springer, New York, 1997 · Zbl 0866.68057
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.