- Source: 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
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
Kata Kunci Pencarian:
- Hans Kelsen
- Dylan Wang
- Semigelanggang
- Uniformitarianisme
- Netflix
- Agama
- Kekristenan
- Filsafat
- RAND Corporation
- Filsafat Bahasa
- Rational series
- Rationality
- Regular language
- Geometric series
- Rational zeta series
- Rational function
- Dyadic rational
- Rational choice model
- Rational variety
- Rational emotive behavior therapy
