Intercodes and the semigroups they generate

Abstract

The study of formal languages through their syntactic monoids has often led to the discovery of interesting relationships between the combinatorial nature of the languages and the algebraic properties of their syntactic monoids. Naturally, by passing from a given language to its syntactic monoid, much information is lost. Nevertheless, if the language in question belongs to a sufficiently restricted class, it is often possible to deduce properties of the language from those of its syntactic monoid. This is indeed the case in our present investigation

We deal with a fairly restricted class of bifix codes called intercodes. These were first studied in [Sh] and subsequently in [Yu] and were introduced as a generalization of comma-free codes (cf. [Be] and [Pe]). In particular we characterize the syntactic monoid of the semigroup generated by an intercode and deduce as a consequence that, given a regular language L, it is decidable whether or not L is an intercode. The question of the decidability of the intercode property was first broached in [Jü] but by methods quite different from those used in this paper.

Keywords:

• Free semigroups
• syntactic monoid of an intercode
• decidability of the intercode property

1991 Mathematics Subject Classification:

• Primary 68R99
• Secondary 20M35
• CR F4
• G2