TY - JOUR
AU - Zoltán Ésik
AU - Werner Kuich
PY - 2000/01/27
Y2 - 2020/11/30
TI - Inductive * -Semirings
JF - BRICS Report Series
JA - BRICS
VL - 7
IS - 27
SE - Articles
DO - 10.7146/brics.v7i27.20158
UR - https://tidsskrift.dk/brics/article/view/20158
AB - One of the most well-known induction principles in computer scienceis the fixed point induction rule, or least pre-fixed point rule. Inductive *-semirings are partially ordered semirings equipped with a star operationsatisfying the fixed point equation and the fixed point induction rule forlinear terms. Inductive *-semirings are extensions of continuous semiringsand the Kleene algebras of Conway and Kozen.We develop, in a systematic way, the rudiments of the theory of inductive*-semirings in relation to automata, languages and power series.In particular, we prove that if S is an inductive *-semiring, then so isthe semiring of matrices Sn*n, for any integer n >= 0, and that if S isan inductive *-semiring, then so is any semiring of power series S((A*)).As shown by Kozen, the dual of an inductive *-semiring may not be inductive. In contrast, we show that the dual of an iteration semiring isan iteration semiring. Kuich proved a general Kleene theorem for continuous semirings, and Bloom and Esik proved a Kleene theorem for all Conway semirings. Since any inductive *-semiring is a Conway semiringand an iteration semiring, as we show, there results a Kleene theorem applicable to all inductive *-semirings. We also describe the structureof the initial inductive *-semiring and conjecture that any free inductive*-semiring may be given as a semiring of rational power series with coefficients in the initial inductive *-semiring. We relate this conjecture torecent axiomatization results on the equational theory of the regular sets.
ER -