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.


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 .

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

The set of formal series is denoted and becomes a semiring under the operations

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

corresponding to the characteristic function of L.

In one can define an operation of iteration expressed as

and formalised as

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 .

See also


  1. 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.

Further reading

This article is issued from Wikipedia - version of the 8/24/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.