• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On the Simplest Centralizer of a Language

Paolo Massazza, Petri Salmela, On the Simplest Centralizer of a Language. RAIRO - Theoretical Informatics and Applications 40(2), 295-301, 2006.

Abstract:

Given a finite alphabet $\Sigma$ and a language $L\subseteq \Sigma^+$,
the centralizer of L is defined as the maximal language commuting with
it. We prove that if the primitive root of the smallest word of L (with
respect to a lexicographic order) is prefix distinguishable in L then
the centralizer of L is as simple as possible, that is, the submonoid
$L^\star$. This lets us obtain a simple proof of a known result
concerning the centralizer of nonperiodic three-word languages.

BibTeX entry:

@ARTICLE{jMaSa06a,
  title = {On the Simplest Centralizer of a Language},
  author = {Massazza, Paolo and Salmela, Petri},
  journal = {RAIRO - Theoretical Informatics and Applications},
  volume = {40},
  number = {2},
  publisher = {EDP Sciences},
  pages = {295-301},
  year = {2006},
  keywords = {Commutation equation, centralizer, lexicographic order},
}

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

Edit publication