no. 6
On conjugacy of languages
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 6, pp. 535-550

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.

Classification : 68R15, 68Q70
Keywords: conjugacy equation, languages, Conway's problem 
@article{ITA_2001__35_6_535_0,
     author = {Cassaigne, Julien and Karhum\"aki, Juhani and Ma\v{n}uch, J\'an},
     title = {On conjugacy of languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {535--550},
     year = {2001},
     publisher = {EDP Sciences},
     volume = {35},
     number = {6},
     mrnumber = {1922294},
     zbl = {1005.68121},
     language = {en},
     url = {https://www.numdam.org/item/ITA_2001__35_6_535_0/}
}
TY  - JOUR
AU  - Cassaigne, Julien
AU  - Karhumäki, Juhani
AU  - Maňuch, Ján
TI  - On conjugacy of languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
SP  - 535
EP  - 550
VL  - 35
IS  - 6
PB  - EDP Sciences
UR  - https://www.numdam.org/item/ITA_2001__35_6_535_0/
LA  - en
ID  - ITA_2001__35_6_535_0
ER  - 
%0 Journal Article
%A Cassaigne, Julien
%A Karhumäki, Juhani
%A Maňuch, Ján
%T On conjugacy of languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 535-550
%V 35
%N 6
%I EDP Sciences
%U https://www.numdam.org/item/ITA_2001__35_6_535_0/
%G en
%F 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) no. 6, pp. 535-550. https://www.numdam.org/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

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

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

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

[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

[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

[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

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

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

[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. | Zbl | MR

[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). | Zbl | MR

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

[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 | Zbl | MR | EuDML