Binary equality words with two b ’s

Štěpán Holub; Jiří Sýkora

Commentationes Mathematicae Universitatis Carolinae (2018)

  • Volume: 59, Issue: 2, page 153-172
  • ISSN: 0010-2628

Abstract

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

How to cite

top

Holub, Štěpán, and Sýkora, Jiří. "Binary equality words with two $b$’s." Commentationes Mathematicae Universitatis Carolinae 59.2 (2018): 153-172. <http://eudml.org/doc/294564>.

@article{Holub2018,
abstract = {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.},
author = {Holub, Štěpán, Sýkora, Jiří},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {equality languages; dual Post correspondence problem; periodicity forcing},
language = {eng},
number = {2},
pages = {153-172},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Binary equality words with two $b$’s},
url = {http://eudml.org/doc/294564},
volume = {59},
year = {2018},
}

TY - JOUR
AU - Holub, Štěpán
AU - Sýkora, Jiří
TI - Binary equality words with two $b$’s
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2018
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 59
IS - 2
SP - 153
EP - 172
AB - 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.
LA - eng
KW - equality languages; dual Post correspondence problem; periodicity forcing
UR - http://eudml.org/doc/294564
ER -

References

top
  1. Barbin-Le R. E., Le Rest M., 10.1016/0304-3975(85)90060-X, Theoret. Comput. Sci. 41 (1985), no. 1, 61–80 (French. English summary). MR0841023DOI10.1016/0304-3975(85)90060-X
  2. Baumslag G., Topics in Combinatorial Group Theory, Lectures in Mathematics ETH Zürich, Birkhäuser, Basel, 1993. MR1243634
  3. Culik K. II, Karhumäki J., 10.1051/ita/1980140403491, RAIRO Inform. Théor. 14 (1980), no. 4, 349–369. MR0607436DOI10.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. MR3315805
  5. Day J. D., Reidenbach D., Schneider J. C., 10.1016/j.tcs.2015.08.033, Theoret. Comput. Sci. 601 (2015), 2–14. MR3396330DOI10.1016/j.tcs.2015.08.033
  6. Ehrenfeucht A., Karhumäki J., Rozenberg G., 10.1016/0304-3975(89)90080-7, Theoret. Comput. Sci. 21 (1982), no. 2, 119–144. MR0677104DOI10.1016/0304-3975(89)90080-7
  7. Ehrenfeucht A., Karhumäki J., Rozenberg G., 10.1016/0021-8693(83)90119-9, J. Algebra 85 (1983), no. 1, 76–85. MR0723068DOI10.1016/0021-8693(83)90119-9
  8. Hadravová J., Structure of Equality Sets, PhD. Thesis, Charles University in Prague, Praha, 2015. 
  9. Hadravová J., Holub Š., Equation x i y j x k = u i v j u k in words, Language and Automata Theory and Applications, Lecture Notes in Comput. Sci., Springer, Cham, 2015, pp. 414–423. MR3344820
  10. Halava V., Harju T., Hirvensalo M., 10.1016/S0304-3975(01)00157-8, Theoret. Comput. Sci. 276 (2002), no. 1–2, 183–204. MR1896352DOI10.1016/S0304-3975(01)00157-8
  11. Halava V., Holub Š., Binary (Generalized) Post Correspondence Problem is in P , TUCS Technical Report, 785, Turku, 2006. MR2081369
  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. Zbl1015.68089MR2177348
  13. Holub Š., 10.1016/S0021-8693(02)00534-3, J. Algebra 259 (2003), no. 1, 1–42. Zbl1010.68101MR1953706DOI10.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. MR1684115
  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., 10.1307/mmj/1028998766, Michigan Math. J. 9 (1962), no. 4, 289–298. MR0162838DOI10.1307/mmj/1028998766
  18. Maňuch J., Defect Theorems and Infinite Words, TUCS Dissertations, 41, Turku, 2002. 
  19. Post E. L., 10.1090/S0002-9904-1946-08555-9, Bull. Amer. Math. Soc. 52 (1946), no. 4, 264–268. Zbl0063.06329MR0015343DOI10.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. MR1469993
  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). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.