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.

Beal, M.P., Burderi, F., Restivo A (2009). Coding partitions of regular sets. INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 19(8), 1011-1023 [10.1142/S0218196709005457].

Coding partitions of regular sets

BURDERI, Fabio;RESTIVO, Antonio
2009-01-01

Abstract

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.
2009
Beal, M.P., Burderi, F., Restivo A (2009). Coding partitions of regular sets. INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 19(8), 1011-1023 [10.1142/S0218196709005457].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/45816
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact