Inductive * -Semirings
DOI:
https://doi.org/10.7146/brics.v7i27.20158Resumé
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 operation
satisfying the fixed point equation and the fixed point induction rule for
linear terms. Inductive *-semirings are extensions of continuous semirings
and 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 is
the semiring of matrices Sn*n, for any integer n >= 0, and that if S is
an 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 is
an 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 semiring
and an iteration semiring, as we show, there results a Kleene theorem
applicable to all inductive *-semirings. We also describe the structure
of 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 to
recent axiomatization results on the equational theory of the regular sets.
Downloads
Publiceret
2000-01-27
Citation/Eksport
Ésik, Z., & Kuich, W. (2000). Inductive * -Semirings. BRICS Report Series, 7(27). https://doi.org/10.7146/brics.v7i27.20158
Nummer
Sektion
Artikler
Licens
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).