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 R ⟨ A ⟩ {\displaystyle R\langle A\rangle } . A formal series is a R-valued function c, on the free monoid A*, which may be written as
∑ w ∈ A ∗ c ( w ) w . {\displaystyle \sum _{w\in A^{*}}c(w)w.}
The set of formal series is denoted R ⟨ ⟨ A ⟩ ⟩ {\displaystyle R\langle \langle A\rangle \rangle } and becomes a semiring under the operations
c + d : w ↦ c ( w ) + d ( w ) {\displaystyle c+d:w\mapsto c(w)+d(w)}
c ⋅ d : w ↦ ∑ u v = w c ( u ) ⋅ d ( v ) {\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. 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
∑ w ∈ L w {\displaystyle \sum _{w\in L}w}
corresponding to the characteristic function of L. In R ⟨ ⟨ A ⟩ ⟩ {\displaystyle R\langle \langle A\rangle \rangle } one can define an operation of iteration expressed as
S ∗ = ∑ n ≥ 0 S n {\displaystyle S^{*}=\sum _{n\geq 0}S^{n}}
and formalised as
c ∗ ( w ) = ∑ u 1 u 2 ⋯ u n = w c ( u 1 ) c ( u 2 ) ⋯ c ( u n ) . {\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 R ⟨ A ⟩ . {\displaystyle R\langle A\rangle .}
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. Vol. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.
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 K {\displaystyle \mathbb {K} } -rational series). ISBN 978-0-521-84425-3. Zbl 1188.68177. 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
