Rational series

In mathematics and computer science, a rational series is a generalisation of the concept of formal power series over a ring to the case when the basic algebraic structure is no longer a ring but a semiring, and the indeterminates adjoined are not assumed to commute. They can be regarded as algebraic expressions of a formal language over a finite alphabet.

Definition

Let R be a semiring and A a finite alphabet.

A non-commutative polynomial over A is a finite formal sum of words over A. They form a semiring ${\displaystyle R\langle A\rangle }$.

A formal series is a R-valued function c, on the free monoid A^*, which may be written as

${\displaystyle \sum _{w\in A^{*}}c(w)w.}$

The set of formal series is denoted ${\displaystyle R\langle \langle A\rangle \rangle }$ and becomes a semiring under the operations

${\displaystyle c+d:w\mapsto c(w)+d(w)}$

${\displaystyle c\cdot d:w\mapsto \sum _{uv=w}c(u)\cdot d(v)}$

A non-commutative polynomial thus corresponds to a function c on A^* of finite support.

In the case when R is a ring, then this is the Magnus ring over R.^[1]

If L is a language over A, regarded as a subset of A^* we can form the characteristic series of L as the formal series

${\displaystyle \sum _{w\in L}w}$

corresponding to the characteristic function of L.

In ${\displaystyle R\langle \langle A\rangle \rangle }$ one can define an operation of iteration expressed as

${\displaystyle S^{*}=\sum _{n\geq 0}S^{n}}$

and formalised as

${\displaystyle c^{*}(w)=\sum _{u_{1}u_{2}\cdots u_{n}=w}c(u_{1})c(u_{2})\cdots c(u_{n}).}$

The rational operations are the addition and multiplication of formal series, together with iteration. A rational series is a formal series obtained by rational operations from ${\displaystyle R\langle A\rangle .}$

See also

• Formal power series
• Rational language
• Rational set
• Hahn series (Malcev–Neumann series)
• Weighted automaton