6533b850fe1ef96bd12a8332
RESEARCH PRODUCT
CODING PARTITIONS OF REGULAR SETS
Marie-pierre BéalAntonio RestivoFabio Burderisubject
MonoidGeneral Mathematicsregular monoid0102 computer and information sciences02 engineering and technologyregular language01 natural sciences[INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL]CombinatoricsRegular language0202 electrical engineering electronic engineering information engineeringPartition (number theory)Finite setComputingMilieux_MISCELLANEOUSMathematicsDiscrete mathematics020206 networking & telecommunicationsPartition of a set16. Peace & justiceFree product010201 computation theory & mathematicscodeuniquely decipherable codecoding partitionRegular setsCoding (social sciences)description
A coding partition of a set of words partitions this set into classes such that whenever a sequence, of minimal length, has two distinct factorizations, the words of these factorizations belong to the same class. The canonical coding partition is the finest coding partition that partitions the set of words in at most one unambiguous class and other classes that localize the ambiguities in the factorizations of finite sequences. We prove that the canonical coding partition of a regular set contains a finite number of regular classes and we give an algorithm for computing this partition. From this we derive a canonical decomposition of a regular monoid into a free product of finitely many regular monoids.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2009-12-01 | International Journal of Algebra and Computation |