1 - Rational series

Summary

This chapter contains the definitions of the basic concepts, namely rational and recognizable series in several noncommuting variables.

We start with the definition of a semiring, followed by the notation for the usual objects in free monoids and formal series. The topology on formal series is briefly introduced.

Section 1.4 contains the definition of rational series, together with some elementary properties and the fact that certain morphisms preserve the rationality of series.

Recognizable series are introduced in Section 1.5. An algebraic characterization is given. We also prove (Theorem 5.1) that the Hadamard product preserves recognizability.

Weighted automata are presented in Section 1.6.

The fundamental theorem of Schützenberger (equivalence between rational and recognizable series, Theorem 7.1) is the concern of the last section. This theorem is the starting point for the developments given in the subsequent chapters.

Semirings

Recall that a semigroup is a set equipped with an associative binary operation, and a monoid is a semigroup having a neutral element for its law.

A semiring is, roughly speaking, a ring without subtraction. More precisely, it is a set K equipped with two operations + and ·(sum and product) such that the following properties hold:

1. (i) (K, +) is a commutative monoid with neutral element denoted by 0.

2. (ii) (K, ·) is a monoid with neutral element denoted by 1.

3. (iii) The product is distributive with respect to the sum.

4. (iv) For all a in K,0a = a0 = 0.