Coding partitions of regular sets

Antonio Restivo, Fabio Burderi, Marie-Pierre Béal

Research output: Contribution to journalArticle

3 Citations (Scopus)


A coding partition of a set of words partitions this set into classes such that whenevera sequence, of minimal length, has two distinct factorizations, the words of these factorizationsbelong to the same class. The canonical coding partition is the finest codingpartition that partitions the set of words in at most one unambiguous class and otherclasses that localize the ambiguities in the factorizations of finite sequences.We prove that the canonical coding partition of a regular set contains a finite numberof regular classes and we give an algorithm for computing this partition. From this wederive a canonical decomposition of a regular monoid into a free product of finitely manyregular monoids.
Original languageEnglish
Pages (from-to)1011-1023
Number of pages13
JournalInternational Journal of Algebra and Computation
Publication statusPublished - 2009

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Coding partitions of regular sets'. Together they form a unique fingerprint.

  • Cite this