[Zurück]

W. Kuich:
"Finite Automata over Conway Semirings";
Vortrag: Recent Advances of Quantitative Models in Computer Science 2021, Thessaloniki (eingeladen); 22.06.2021 - 23.06.2021.

A starsemiring satisfying the sum - star - equation and the product - star - equation is called Conway semiring. Each complete starsemiring is a Conway semiring. The semirings of nxn - matrices with entries in a Conway semiring and of power series with coefficients in a Conway semiring are again Conway semirings.
Let S be a Conway semiring and S´ be a subset of S containing 0 and 1. A finite S´ - automaton with state set {1, ... , n} is defined by an transition matrix M, an initial row vector I and a final column vector P, all of dimension n with entries in S´. Its behavior is given by IM*P.
Let Rec(S´) be the collection of the behaviors of all finite S´ - automata. Denote by Rat(S´) the least starsemiring closed under the rational operations +, ., * and containing S´. Then we prove the Kleene theorem Rec(S´) = Rat(S´).
If the basic semiring is a power series seming with coefficients in a Conway semiring, we prove a Kleene - Schützenberger theorem.