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
topHow 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.
- J.H. Conway, Regular algebra and finite machines. Chapman Hall (1971).
- S. Eilenberg, Automata, languages and machines. Academic Press (1974).
- 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).
- M. Lothaire, Combinatorics on words. Addison-Wesley (1983).
- 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).
- D. Perrin, Codes conjugués. Inform. and Control20 (1972) 222-231.
- W. Plandowski, Satisfiability of word equations with constants is in PSPACE, in Proc. of FOCS'99. IEEE (1999) 495-500.
- B. Ratoandramanana, Codes et motifs. RAIRO: Theoret. Informatics Appl.23 (1989) 425-444.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.