rational series

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

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

:$\backslash sum\_\{w\; \backslash in\; A^*\}\; c(w)\; w\; .$

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

:$c+d\; :\; w\; \backslash mapsto\; c(w)\; +\; d(w)$

:$c\backslash cdot\; d\; :\; w\; \backslash mapsto\; \backslash sum\_\{uv\; =\; w\}\; c(u)\; \backslash 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.{{cite book | first=Helmut | last=Koch | title=Algebraic Number Theory | publisher=Springer-Verlag | year=1997 | isbn=3-540-63003-1 | zbl=0819.11044 | series=Encycl. Math. Sci. | volume=62 | edition=2nd printing of 1st | page=167 }}

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

:$\backslash sum\_\{w\; \backslash in\; L\}\; w$

corresponding to the characteristic function of L.

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

:$S^*\; =\; \backslash sum\_\{n\; \backslash ge\; 0\}\; S^n$

and formalised as

:$c^*(w)\; =\; \backslash sum\_\{u\_1\; u\_2\; \backslash cdots\; u\_n\; =\; w\}\; c(u\_1)c(u\_2)\; \backslash 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\backslash langle\; A\; \backslash rangle.$

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

{{reflist}}

• {{cite book | last1=Berstel | first1=Jean | author-link1=Jean Berstel | last2=Reutenauer | first2=Christophe | title=Noncommutative rational series with applications | series=Encyclopedia of Mathematics and Its Applications | volume=137 | location=Cambridge | publisher=Cambridge University Press | year=2011 | isbn=978-0-521-19022-0 | zbl=1250.68007 }}

• {{cite book | last=Sakarovitch | first=Jacques | title=Elements of automata theory | others=Translated from the French by Reuben Thomas | location=Cambridge | publisher=Cambridge University Press | year=2009 | isbn=978-0-521-84425-3 | zbl=1188.68177 | at=Part IV (where they are called $\backslash mathbb\{K\}$-rational series)}}
• 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

Category:Abstract algebra

Category:Formal languages

Category:Series (mathematics)

{{abstract-algebra-stub}}