[Back]

W. Kuich:
"Finite Automata over Conway Semirings";
Talk: Recent Advances of Quantitative Models in Computer Science 2021, Thessaloniki (invited); 2021-06-22 - 2021-06-23.

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.