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 [math]\displaystyle{ R\langle A \rangle }[/math].

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

[math]\displaystyle{ \sum_{w \in A^*} c(w) w . }[/math]

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

[math]\displaystyle{ c+d : w \mapsto c(w) + d(w) }[/math]

[math]\displaystyle{ c\cdot d : w \mapsto \sum_{uv = w} c(u) \cdot d(v) }[/math]

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.

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

[math]\displaystyle{ \sum_{w \in L} w }[/math]

corresponding to the characteristic function of L.

In [math]\displaystyle{ R\langle\langle A \rangle\rangle }[/math] one can define an operation of iteration expressed as

[math]\displaystyle{ S^* = \sum_{n \ge 0} S^n }[/math]

and formalised as

[math]\displaystyle{ c^*(w) = \sum_{u_1 u_2 \cdots u_n = w} c(u_1)c(u_2) \cdots c(u_n) . }[/math]

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 [math]\displaystyle{ R\langle A \rangle. }[/math]

See also

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

References

• Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. 

Further reading

• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. Part IV (where they are called [math]\displaystyle{ \mathbb{K} }[/math]-rational series). ISBN 978-0-521-84425-3. 
• Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. Handbook of Weighted Automata, 3–28. doi:10.1007/978-3-642-01492-5_1
• Sakarovitch, J. Rational and Recognisable Power Series. Handbook of Weighted Automata, 105–174 (2009). doi:10.1007/978-3-642-01492-5_4
• W. Kuich. Semirings and formal power series: Their relevance to formal languages and automata theory. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 1, Chapter 9, pages 609–677. Springer, Berlin, 1997