# On conjugacy of languages

Julien Cassaigne; Juhani Karhumäki; Ján Maňuch

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

- Volume: 35, Issue: 6, page 535-550
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCassaigne, Julien, Karhumäki, Juhani, and Maňuch, Ján. "On conjugacy of languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.6 (2001): 535-550. <http://eudml.org/doc/92683>.

@article{Cassaigne2001,

abstract = {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.},

author = {Cassaigne, Julien, Karhumäki, Juhani, Maňuch, Ján},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {conjugacy equation; languages; Conway’s problem},

language = {eng},

number = {6},

pages = {535-550},

publisher = {EDP-Sciences},

title = {On conjugacy of languages},

url = {http://eudml.org/doc/92683},

volume = {35},

year = {2001},

}

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

PB - EDP-Sciences

VL - 35

IS - 6

SP - 535

EP - 550

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

LA - eng

KW - conjugacy equation; languages; Conway’s problem

UR - http://eudml.org/doc/92683

ER -

## References

top- [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. MR1469998
- [2] Ch. Choffrut, J. Karhumäki and N. Ollinger, The commutation of finite sets: A challenging problem. Theoret. Comput. Sci. 273 (2002) 69-79. Zbl1014.68128MR1872443
- [3] J.H. Conway, Regular algebra and finite machines. Chapman Hall (1971). Zbl0231.94041
- [4] S. Eilenberg, Automata, languages and machines. Academic Press (1974). Zbl0317.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). MR1905123
- [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. Zbl0984.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. Zbl0973.68115
- [9] E. Leiss, Language equations. Springer (1998). Zbl0926.68064MR1724110
- [10] M. Lothaire, Combinatorics on words. Addison-Wesley (1983). Zbl0514.20045MR675953
- [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. Zbl0221.20076MR251158
- [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). Zbl0396.20037MR470107
- [13] D. Perrin, Codes conjugués. Inform. and Control 20 (1972) 222-231. Zbl0254.94015MR345711
- [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. Zbl0689.68102MR1036694

## NotesEmbed ?

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