# On Conjugacy of Languages

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

RAIRO - Theoretical Informatics and Applications (2010)

- 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 35.6 (2010): 535-550. <http://eudml.org/doc/222000>.

@article{Cassaigne2010,

abstract = {
We say that two languages X and Y are conjugates if they satisfy
the conjugacy equationXZ = 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},

keywords = {Conjugacy equation; languages; Conway's Problem.; conjugacy equation},

language = {eng},

month = {3},

number = {6},

pages = {535-550},

publisher = {EDP Sciences},

title = {On Conjugacy of Languages},

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

volume = {35},

year = {2010},

}

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

DA - 2010/3//

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 equationXZ = 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.; conjugacy equation

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

ER -

## References

top- 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.
- Ch. Choffrut, J. Karhumäki and N. Ollinger, The commutation of finite sets: A challenging problem. Theoret. Comput. Sci.273 (2002) 69-79. Zbl1014.68128
- J.H. Conway, Regular algebra and finite machines. Chapman Hall (1971). Zbl0231.94041
- S. Eilenberg, Automata, languages and machines. Academic Press (1974). Zbl0317.94045
- 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).
- T. Harju and I. Petre, On commutation and primitive roots of codes. TUCS Technical Report 402 (2001).
- 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.
- 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.
- E. Leiss, Language equations. Springer (1998). Zbl0454.68105
- M. Lothaire, Combinatorics on words. Addison-Wesley (1983). Zbl0514.20045
- 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.
- 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). Zbl0371.20047
- D. Perrin, Codes conjugués. Inform. and Control20 (1972) 222-231. Zbl0254.94015
- W. Plandowski, Satisfiability of word equations with constants is in PSPACE, in Proc. of FOCS'99. IEEE (1999) 495-500. Zbl1346.68113
- B. Ratoandramanana, Codes et motifs. RAIRO: Theoret. Informatics Appl.23 (1989) 425-444. Zbl0689.68102

## NotesEmbed ?

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