Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Commutation Problems on Sets o...

Commutation Problems on Sets of Words and Formal Power Series

Ion Petre, Commutation Problems on Sets of Words and Formal Power Series. TUCS Dissertations 38. Turku Centre for Computer Science, 2002.

Abstract:

We study in this thesis several problems related to commutation on
sets of words and on formal power series. We investigate the
notion of semilinearity for formal power series in commuting
variables, introducing two families of series -the semilinear and
the bounded series- both natural generalizations of the
semilinear languages, and we study their behaviour under rational
operations, morphisms, Hadamard product, and difference. Turning
to commutation on sets of words, we then study the notions of
centralizer of a language -the largest set commuting with a
language-, of root and of primitive root of a set of words. We
answer a question raised by Conway more than thirty years ago
-asking whether or not the centralizer of any rational language
is rational- in the case of periodic, binary, and ternary sets of
words, as well as for rational omega-codes, the most general
results on this problem. We also prove that any code has a unique
primitive root and that two codes commute if and only if they have
the same primitive root, thus solving two conjectures of
Ratoandromanana, 1989. Moreover, we prove that the commutation
with an omega-code X can be characterized similarly as in
free monoids: a language commutes with X if and only if it is a
union of powers of the primitive root of X.

Files:

Full publication in PDF-format

BibTeX entry:

@PHDTHESIS{phdPetre02a,
  title = {Commutation Problems on Sets of Words and Formal Power Series},
  author = {Petre, Ion},
  number = {38},
  series = {TUCS Dissertations},
  school = {Turku Centre for Computer Science},
  year = {2002},
  ISBN = {951-29-2270-3},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication