Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Commutation with Codes

Commutation with Codes

Juhani Karhumäki, Michel Latteux, Ion Petre, Commutation with Codes. Theoretical Computer Science 340(2), 322–333, 2005.

Abstract:

The centralizer of a set of words $X$ is the largest set of words
$\cc(X)$ commuting with~$X$: $X\cc(X)=\cc(X)X$. It has been a long
standing open question due to Conway, 1971, whether the centralizer
of any rational set is rational. While the answer turned out to be
negative in general, see Kunc 2004, we prove here that the situation
is different for codes: the centralizer of any rational code is
rational and if the code is finite, then the centralizer is finitely
generated. This result has been previously proved only for binary
and ternary sets of words in a series of papers by the authors and
for prefix codes in an ingenious paper by
Ratoandromanana~1989~--~many of the techniques we use in this paper
follow her ideas. We also give in this paper an elementary proof for
the prefix case.

BibTeX entry:

@ARTICLE{jKaLaPe05a,
  title = {Commutation with Codes},
  author = {Karhumäki, Juhani and Latteux, Michel and Petre, Ion},
  journal = {Theoretical Computer Science},
  volume = {340},
  number = {2},
  pages = {322–333},
  year = {2005},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics, Computational Biomodeling Laboratory (Combio Lab)

Publication Forum rating of this publication: level 2

Edit publication