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

Abstract

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

How to cite

top

Cassaigne, 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
  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.  
  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.68128
  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).  
  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.  
  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.  
  9. E. Leiss, Language equations. Springer (1998).  Zbl0454.68105
  10. M. Lothaire, Combinatorics on words. Addison-Wesley (1983).  Zbl0514.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.  
  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).  Zbl0371.20047
  13. D. Perrin, Codes conjugués. Inform. and Control20 (1972) 222-231.  Zbl0254.94015
  14. W. Plandowski, Satisfiability of word equations with constants is in PSPACE, in Proc. of FOCS'99. IEEE (1999) 495-500.  Zbl1346.68113
  15. B. Ratoandramanana, Codes et motifs. RAIRO: Theoret. Informatics Appl.23 (1989) 425-444.  Zbl0689.68102

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.