On conjugacy of languages
Cassaigne, Julien ; Karhumäki, Juhani ; Maňuch, Ján
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001), p. 535-550 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We say that two languages X and Y are conjugates if they satisfy the conjugacy equation XZ=ZY for some language Z. We study several problems associated with this equation. For example, we characterize all sets which are conjugated via a two-element biprefix set Z, as well as all two-element sets which are conjugates.

Publié le : 2001-01-01
Classification:  68R15,  68Q70 
@article{ITA_2001__35_6_535_0,
     author = {Cassaigne, Julien and Karhum\"aki, Juhani and Ma\v nuch, J\'an},
     title = {On conjugacy of languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {35},
     year = {2001},
     pages = {535-550},
     mrnumber = {1922294},
     zbl = {1005.68121},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2001__35_6_535_0}
}

Cassaigne, Julien; Karhumäki, Juhani; Maňuch, Ján. On conjugacy of languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) pp. 535-550. http://gdmltest.u-ga.fr/item/ITA_2001__35_6_535_0/

[1] Ch. Choffrut and J. Karhumäki, Combinatorics of words, in Handbook of Formal Languages, Vol. 1, edited by G. Rozenberg and A. Salomaa. Springer (1997) 329-438. | MR 1469998

[2] Ch. Choffrut, J. Karhumäki and N. Ollinger, The commutation of finite sets: A challenging problem. Theoret. Comput. Sci. 273 (2002) 69-79. | MR 1872443 | Zbl 1014.68128

[3] J.H. Conway, Regular algebra and finite machines. Chapman Hall (1971). | Zbl 0231.94041

[4] S. Eilenberg, Automata, languages and machines. Academic Press (1974). | Zbl 0317.94045

[5] T. Harju, J. Karhumäki and W. Plandowski, Independent systems of equations, Chap. 14 of Algebraic combinatorics on words, by M. Lothaire. Cambridge University Press (2002). | MR 1905123

[6] T. Harju and I. Petre, On commutation and primitive roots of codes. TUCS Technical Report 402 (2001).

[7] J. Karhumäki, Combinatorial and computational problems of finite sets of words, in Proc. of MCU'01. Springer, Lecture Notes in Comput. Sci. 2055 (2001) 69-81. | Zbl 0984.68118

[8] J. Karhumäki and I. Petre, On the centralizer of a finite set, in Proc. of ICALP'00. Springer, Lecture Notes in Comput. Sci. 1853 (2000) 536-546. | Zbl 0973.68115

[9] E. Leiss, Language equations. Springer (1998). | MR 1724110 | Zbl 0926.68064

[10] M. Lothaire, Combinatorics on words. Addison-Wesley (1983). | MR 675953 | Zbl 0514.20045

[11] A. Lentin and M.-P. Schützenberger, A combinatorial problem in the theory of free monoids, in Combinatorial Mathematics and its Applications. Univ. North Carolina Press (1969) 128-144. | MR 251158 | Zbl 0221.20076

[12] G.S. Makanin, The problem of solvability of equations in a free semigroup. Mat. Sb. 103 (1977) 147-236 (English transl. in Math USSR Sb. 32 (1979) 129-198). | MR 470107 | Zbl 0396.20037

[13] D. Perrin, Codes conjugués. Inform. and Control 20 (1972) 222-231. | MR 345711 | Zbl 0254.94015

[14] W. Plandowski, Satisfiability of word equations with constants is in PSPACE, in Proc. of FOCS'99. IEEE (1999) 495-500.

[15] B. Ratoandramanana, Codes et motifs. RAIRO: Theoret. Informatics Appl. 23 (1989) 425-444. | Numdam | MR 1036694 | Zbl 0689.68102