On Conjugacy of Languages
Institut de Mathématiques de Luminy – CNRS/FRUMAM,
13288 Marseille Cedex 9, France; (firstname.lastname@example.org)
2 Department of Mathematics and TUCS, University of Turku, 20014 Turku, Finland; (email@example.com)
3 TUCS and Department of Mathematics, Datacity, Lemminkäisenkatu 14A, 20520 Turku, Finland; (firstname.lastname@example.org)
Revised: 15 February 2002
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.
Mathematics Subject Classification: 68R15 / 68Q70
Key words: Conjugacy equation / languages / Conway's Problem.
© EDP Sciences, 2001