| Title:
|
Binary equality words with two $b$'s (English) |
| Author:
|
Holub, Štěpán |
| Author:
|
Sýkora, Jiří |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
59 |
| Issue:
|
2 |
| Year:
|
2018 |
| Pages:
|
153-172 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
equality languages |
| Keyword:
|
dual Post correspondence problem |
| Keyword:
|
periodicity forcing |
| MSC:
|
68R15 |
| idZBL:
|
Zbl 06940860 |
| idMR:
|
MR3815682 |
| DOI:
|
10.14712/1213-7243.2015.247 |
| . |
| Date available:
|
2018-06-20T08:35:55Z |
| Last updated:
|
2020-07-06 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147249 |
| . |
| Reference:
|
[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). MR 0841023, 10.1016/0304-3975(85)90060-X |
| Reference:
|
[2] Baumslag G.: Topics in Combinatorial Group Theory.Lectures in Mathematics ETH Zürich, Birkhäuser, Basel, 1993. MR 1243634 |
| Reference:
|
[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. MR 0607436, 10.1051/ita/1980140403491 |
| Reference:
|
[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 |
| Reference:
|
[5] Day J. D., Reidenbach D., Schneider J. C.: Periodicity forcing words.Theoret. Comput. Sci. 601 (2015), 2–14. MR 3396330, 10.1016/j.tcs.2015.08.033 |
| Reference:
|
[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. MR 0677104, 10.1016/0304-3975(89)90080-7 |
| Reference:
|
[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. MR 0723068, 10.1016/0021-8693(83)90119-9 |
| Reference:
|
[8] Hadravová J.: Structure of Equality Sets.PhD. Thesis, Charles University in Prague, Praha, 2015. |
| Reference:
|
[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 |
| Reference:
|
[10] Halava V., Harju T., Hirvensalo M.: Binary (generalized) Post correspondence problem.Theoret. Comput. Sci. 276 (2002), no. 1–2, 183–204. MR 1896352, 10.1016/S0304-3975(01)00157-8 |
| Reference:
|
[11] Halava V., Holub Š.: Binary (Generalized) Post Correspondence Problem is in $P$.TUCS Technical Report, 785, Turku, 2006. MR 2081369 |
| Reference:
|
[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, MR 2177348 |
| Reference:
|
[13] Holub Š.: Binary equality sets are generated by two words.J. Algebra 259 (2003), no. 1, 1–42. Zbl 1010.68101, MR 1953706, 10.1016/S0021-8693(02)00534-3 |
| Reference:
|
[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. |
| Reference:
|
[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 |
| Reference:
|
[16] Lothaire M.: Algebraic Combinatorics on Words.Encyclopedia of Mathematics and Its Applications, 90, Cambridge University Press, Cambridge, 2002. |
| Reference:
|
[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. MR 0162838, 10.1307/mmj/1028998766 |
| Reference:
|
[18] Maňuch J.: Defect Theorems and Infinite Words.TUCS Dissertations, 41, Turku, 2002. |
| Reference:
|
[19] Post E. L.: A variant of a recursively unsolvable problem.Bull. Amer. Math. Soc. 52 (1946), no. 4, 264–268. Zbl 0063.06329, MR 0015343, 10.1090/S0002-9904-1946-08555-9 |
| Reference:
|
[20] Rozenberg G., Salomaa A., eds.: Handbook of Formal Languages, Vol. 1: Word, Language, Grammar.Springer, New York, 1997. MR 1469993 |
| Reference:
|
[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). |
| . |
