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

Abstract

top
We say that two languages X and Y are conjugates if they satisfy the conjugacy equation X Z = Z Y for some language Z . We study several problems associated with this equation. For example, we characterize all sets which are conjugated v i a 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 - 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. [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. [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. [3] J.H. Conway, Regular algebra and finite machines. Chapman Hall (1971). Zbl0231.94041
  4. [4] S. Eilenberg, Automata, languages and machines. Academic Press (1974). Zbl0317.94045
  5. [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. [6] T. Harju and I. Petre, On commutation and primitive roots of codes. TUCS Technical Report 402 (2001). 
  7. [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. [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. [9] E. Leiss, Language equations. Springer (1998). Zbl0926.68064MR1724110
  10. [10] M. Lothaire, Combinatorics on words. Addison-Wesley (1983). Zbl0514.20045MR675953
  11. [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. [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. [13] D. Perrin, Codes conjugués. Inform. and Control 20 (1972) 222-231. Zbl0254.94015MR345711
  14. [14] W. Plandowski, Satisfiability of word equations with constants is in PSPACE, in Proc. of FOCS’99. IEEE (1999) 495-500. 
  15. [15] B. Ratoandramanana, Codes et motifs. RAIRO: Theoret. Informatics Appl. 23 (1989) 425-444. Zbl0689.68102MR1036694

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.