Unambiguous monoids of relations
Jean Berstel, Dominique Perrin, Christophe Reutenauer · Cambridge University Press eBooks · 2009
To each unambiguous automaton corresponds a monoid of relations which is also called unambiguous. A relation in this monoid corresponds to each word and the computations on words are replaced by computations on relations. The principal result of this chapter (Theorem 9.4.1) shows that very thin codes are exactly the codes for which the associated monoid satisfies a finiteness condition: it contains relations of finite positive rank. This result explains why thin codes constitute a natural family containing the recognizable codes. It makes it possible to prove properties of thin codes by reasoning in finite structures. As a consequence, we shall give, for example, an alternative proof of the maximality of thin complete codes which does not use probabilities. The main result also allows us to define, for each thin code, some important parameters: the degree and the group of the code. The group of a thin code is a finite permutation group. The degree of the code is the number of elements on which this group acts. These parameters reflect properties of words by means of “interpretations”. For example, the synchronized codes in the sense of Chapter 3 are those having degree 1. This chapter is organized in the following manner. In Section 9.1, basic properties of unambiguous monoids of relations are proved. These monoids constantly appear in what follows, since each unambiguous automaton gives rise to an unambiguous monoid of relations. In Section 9.2, we define two representations of unambiguous monoids of relations, called the R and L -representations or Schützenberger representations.