Partial Conway and Iteration Semirings

• Autorzy: Bloom S.L. , Ésik Z. , Kuich W.
• Języki publikacji: EN

Abstrakty

EN

A Conway semiring is a semiring S equipped with a unary operation *: S →S, always called 'star', satisfying the sum star and product star identities. It is known that these identities imply a Kleene type theorem. Some computationally important semirings, such as N or N^{rat}((σ)) of rational power series of words on σ with coefficients in N, cannot have a total star operation satisfying the Conway identities. We introduce here partial Conway semirings, which are semirings S which have a star operation defined only on an ideal of S; when the arguments are appropriate, the operation satisfies the above identities. We develop the general theory of partial Conway semirings and prove a Kleene theorem for this generalization.

Słowa kluczowe

EN

Conway semiring; iteration semiring; Kleene theorem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 86, nr 1-2
• Strony: 19--40
• Opis fizyczny: bibliogr. 19 poz.

Twórcy

autor

Bloom S.L.

autor

Ésik Z.

autor

Kuich W.

• GRLMC, Rovira i Virgili University, Tarragona, Spain,

Bibliografia

• [1] J. Berstel and Ch. Reutenauer, Rational Series and Their Languages, Springer, 1988. Verison of October 19, 2007, http://www-igm.univ-mlv.fr/ berstel/.
• [2] S.L. Bloom and Z. 'Esik, Matrix and matricial iteration theories, Part I, J. Comput. Sys. Sci., 46(1993), 381-408.
• [3] S.L. Bloom and Z. 'Esik, Iteration Theories: The Equational Logic of Iterative Processes, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1993.
• [4] S.L. Bloom and Z. 'Esik, Axiomatizing rational power series, to appear.
• [5] S. Bloom, S. Ginali and J.D. Rutlege, Scalar and vector iteration, J. Computer System Sciences, 14(1977), 251-256.
• [6] J.C. Conway. Regular Algebra and Finite Machines, Chapman and Hall, London, 1971.
• [7] M. Droste andW. Kuich, Semirings and formal power series, in: Handbook of Weighted Automata, Springer, to appear.
• [8] S. Eilenberg, Automata, Languages, and Machines. vol. A, Academic Press, 1974.
• [9] C.C. Elgot, Monadic computation and iterative algebraic theories, in: Logic Colloquium 1973, Studies in Logic, J.C. Shepherdson, editor, volume 80, North Holland, Amsterdam, 1975, 175-230.
• [10] C.C. Elgot, Matricial theories, J. of Algebra, 42(1976), 391-421.
• [11] Z. 'Esik, Group axioms for iteration, Information and Computation, 148(1999), 131-180.
• [12] Z. 'Esik and W. Kuich, Inductive _-semirings, Theoret. Comput. Sci., 324(2004), 3-33.
• [13] Z. 'Esik and W. Kuich, Equational axioms for a theory of automata, in: Formal Languages and Applications, Studies in Fuzziness and Soft Computing 148, Springer, 2004, 183-196.
• [14] J.S. Golan, Semirings and their Applications, Kluwer Academic Publishers, 1999.
• [15] G. Gr¨atzer, Universal Algebra, Springer, 1979.
• [16] D. Krob, Complete systems of B-rational identities, Theoretical Computer Science, 89(1991), 207-343.
• [17] D. Krob, Matrix versions of aperiodic K-rational identities, Theoretical Informatics and Appllications, 25(1991), 423-444.
• [18] V.N. Redko, On the determining totality of relations of an algebra of regular events (in Russian), Ukrainian Math. Z., 16(1964), 120-126.
• [19] V.N. Redko, On algebra of commutative events (in Russian), Ukrainian Math. Z, 16(1964), 185-195.