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
Mots clés : 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},
publisher = {EDP-Sciences},
volume = {35},
number = {6},
year = {2001},
zbl = {1005.68121},
mrnumber = {1922294},
language = {en},
url = {http://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
DA  - 2001///
SP  - 535
EP  - 550
VL  - 35
IS  - 6
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2001__35_6_535_0/
UR  - https://zbmath.org/?q=an%3A1005.68121
UR  - https://www.ams.org/mathscinet-getitem?mr=1922294
LA  - en
ID  - ITA_2001__35_6_535_0
ER  - 
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. http://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 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. | EuDML 92342 | Numdam | MR 1036694 | Zbl 0689.68102