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 noncommutative polynomial over A is a finite formal sum of words over A. They form a semiring $R\langle A\rangle$ .

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

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

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

c+d:w\mapsto c(w)+d(w)\

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

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

corresponding to the characteristic function of L.

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

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

and formalised as

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\langle A\rangle$ .

References

↑ Koch, Helmut (1997). Algebraic Number Theory. Encycl. Math. Sci. 62 (2nd printing of 1st ed.). Springer-Verlag. p. 167. ISBN 3-540-63003-1. Zbl 0819.11044.

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. Zbl 1250.68007.

Rational series

Definition

See also

References

Further reading