You are here: TUCS > PUBLICATIONS > Publication Search > Conjugacy of Finite Biprefix C...
- TUCS Publication Series
- How to Publish in TUCS Series
- Publication Search
- Publication Graph
- Publication Input
- Publication Input Guide
- JuFo Browser
Conjugacy of Finite Biprefix Codes
Julien Cassaigne, Juhani Karhumäki, Petri Salmela, Conjugacy of Finite Biprefix Codes. In: Theory and Applications of Language Equations, Proceedings of the 1st International Workshop, TUCS General Publication, 33-42, Turku Centre for Computer Science, 2007.
Abstract:
Two languages <i>X</i> and <i>Y</i> are called conjugates, if they
satisfy the conjugacy equation <i>XZ = ZY</i> for some non-empty
language <i>Z</i>. We will compare solutions of this equation with
those of the corresponding equation of words and study the case of
finite biprefix codes <i>X</i> and <i>Y</i>. We show that the maximal
<i>Z</i> in this case is rational. We will also characterize <i>X</i>
and <i>Y</i> in the case where they are both finite biprefix codes.
This yields decidability of conjugacy of two finite biprefix codes.
BibTeX entry:
@INPROCEEDINGS{inpCaKaSa07a,
title = {Conjugacy of Finite Biprefix Codes},
booktitle = {Theory and Applications of Language Equations, Proceedings of the 1st International Workshop},
author = {Cassaigne, Julien and Karhumäki, Juhani and Salmela, Petri},
number = {44},
series = {TUCS General Publication},
publisher = {Turku Centre for Computer Science},
pages = {33-42},
year = {2007},
keywords = {Language equations, biprefix codes, conjugacy},
}
Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics