Outfix and infix codes and related classes of languages

摘要

A language L such that no word in L is a proper factor of another word in L is said to be an infix code. A language L such that no word in L can be obtained from another word in L by the cancellation of a proper factor is called an outfix code. We derive properties of infix and outfix codes which describe their relation to other classes of codes and which determine their combinatorial structures. In particular, we consider closure properties of these and related classes of codes, maximal codes within these classes, the syntactic monoids of such codes, and the connection of these codes with binary relations on the free monoid.