Precircular codes and periodic biinfinite words. (English) Zbl 0790.94007

Summary: The aim of decoding, of factorizing in a single way, biinfinite words with a finitary language leads us to consider two distinct notions of factorization for biinfinite words. For one of these notions, requiring singleness of decoding periodic biinfinite words leads us to study circular codes. The other notion leads us to define the new notion of precircular codes. Precircular codes are defined and analyzed. The family of precircular codes is compared to the family of circular codes and to the family of almost circular codes. The structure of two-element precircular codes is determined. Codes and precircular codes are characterized by their way of acting upon periodic biinfinite words.


94A45 Prefix, length-variable, comma-free codes
68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
94B35 Decoding
94B60 Other types of codes
Full Text: DOI