We say that two languages and are conjugates if they satisfy the conjugacy equation for some language . We study several problems associated with this equation. For example, we characterize all sets which are conjugated a two-element biprefix set , as well as all two-element sets which are conjugates.
@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}, mrnumber = {1922294}, zbl = {1005.68121}, language = {en}, url = {http://archive.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 - http://archive.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 http://archive.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, Volume 35 (2001) no. 6, pp. 535-550. http://archive.numdam.org/item/ITA_2001__35_6_535_0/
[1] Combinatorics of words, in Handbook of Formal Languages, Vol. 1, edited by G. Rozenberg and A. Salomaa. Springer (1997) 329-438. | MR
and ,[2] The commutation of finite sets: A challenging problem. Theoret. Comput. Sci. 273 (2002) 69-79. | MR | Zbl
, and ,[3] Regular algebra and finite machines. Chapman Hall (1971). | Zbl
,[4] Automata, languages and machines. Academic Press (1974). | Zbl
,[5] Independent systems of equations, Chap. 14 of Algebraic combinatorics on words, by M. Lothaire. Cambridge University Press (2002). | MR
, and ,[6] On commutation and primitive roots of codes. TUCS Technical Report 402 (2001).
and ,[7] 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] On the centralizer of a finite set, in Proc. of ICALP'00. Springer, Lecture Notes in Comput. Sci. 1853 (2000) 536-546. | Zbl
and ,[9] Language equations. Springer (1998). | MR | Zbl
,[10] Combinatorics on words. Addison-Wesley (1983). | MR | Zbl
,[11] A combinatorial problem in the theory of free monoids, in Combinatorial Mathematics and its Applications. Univ. North Carolina Press (1969) 128-144. | MR | Zbl
and ,[12] 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 | Zbl
,[13] Codes conjugués. Inform. and Control 20 (1972) 222-231. | MR | Zbl
,[14] Satisfiability of word equations with constants is in PSPACE, in Proc. of FOCS'99. IEEE (1999) 495-500.
,[15] Codes et motifs. RAIRO: Theoret. Informatics Appl. 23 (1989) 425-444. | EuDML | Numdam | MR | Zbl
,