Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > On the Centralizer of a Ration...

On the Centralizer of a Rational Language and the Fixed Point Method

Petri Salmela, On the Centralizer of a Rational Language and the Fixed Point Method. 2005.

Abstract:

<p>
In this work we consider the commutation of rational languages. Especially we study the centralizer, the maximal language commuting with a given language and Conway’s problem connected to it. J.H. Conway asked in 1971 (Regular algebra and Finite Machines, Chapman Hall,1971), if the centralizer of a rational language is also rational. The question remained unanswered for a long time, until just recently M. Kunc gave it the negative answer.
</p>
<p>
We shall present the fixed point approach introduced by J. Karhumäki (Challenges of Commutation - An advertisement, in: FCT 2001, R. Freivalds, (ed.), Lecture Notes in Computer Science 2138, Springer-Verlag, New York 2001, pp. 15-23). This approach is an iterative method for finding the centralizer of a given language as a maximal fixed
point of certain language operation. For most of rational languages this method gives the result rather soon, but on some cases it leads to an infinit computation.
</p>
<p>
First we introduce some required tools and notations. Next we give a few results on the centralizer in general and in some special cases. Finally we study, how the fixed point approach behaves on some selected examples. We discuss few cases where approach is successful and also some cases for which the approach fails. We show that the fixed point approach can fail even when the given language is finite.
</p>
<p>
As a computing tool, we have used the computer program called Grail+. This program is developed in the University of Western Ontario, Canada, and improved in the University of Turku.
</p>
<p>
Keywords: rational languages, commutation, the centralizer, fixed point approach, Conway’s problem.
</p>

BibTeX entry:

@LICTHESIS{licSalmela05a,
  title = {On the Centralizer of a Rational Language and the Fixed Point Method},
  author = {Salmela, Petri},
  year = {2005},
  keywords = {rational languages, automata, commutation, the centralizer, Conway's problem, fixed point approach},
}

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

Edit publication