article

Partial Conway and Iteration Semirings

Authors:

Stephen L. Bloom,

Werner KuichAuthors Info & Claims

Fundamenta Informaticae, Volume 86, Issue 1,2

Pages 19 - 40

Published: 01 April 2008 Publication History

Abstract

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.

References

[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. Ésik, Matrix and matricial iteration theories, Part I, J. Comput. Sys. Sci., 46(1993), 381- 408.

[3]

S.L. Bloom and Z. Ésik, Iteration Theories: The Equational Logic of Iterative Processes, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1993.

[4]

S.L. Bloom and Z. Ésik, 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 and W. 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. Ésik, Group axioms for iteration, Information and Computation, 148(1999), 131-180.

[12]

Z. Ésik and W. Kuich, Inductive *-semirings, Theoret. Comput. Sci., 324(2004), 3-33.

Digital Library

[13]

Z. Ésik 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ätzer, 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. ¿., 16(1964), 120-126.

[19]

V.N. Redko, On algebra of commutative events (in Russian), Ukrainian Math. ¿., 16(1964), 185-195

Cited By

Kostolányi P(2019)A Unifying Approach to Algebraic Systems Over SemiringsTheory of Computing Systems10.1007/s00224-018-9895-963:3(615-633)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00224-018-9895-9
Ésik ZHajgató T(2014)On the structure of free iteration semiringsJournal of Automata, Languages and Combinatorics10.5555/3173474.317348019:1(57-66)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.5555/3173474.3173480
Abbad HLaugerotte É(2013)Computing weightsProceedings of the 18th international conference on Implementation and Application of Automata10.1007/978-3-642-39274-0_4(24-35)Online publication date: 16-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39274-0_4
Show More Cited By

Index Terms

Partial Conway and Iteration Semirings

Recommendations

Partial Conway and Iteration Semirings

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 ...
Partial conway and iteration semiring-semimodule pairs
Algebraic Foundations in Computer Science

A Conway semiring is a semiring S equipped with a unary operation ^*:S→S, called “star”, satisfying the sum star and product star identities. A Conway semiring-semimodule pair consists of a Conway semiring S and a left S-semimodule V together with a ...
Iteration Semirings
DLT '08: Proceedings of the 12th international conference on Developments in Language Theory

A Conway semiring is a semiring S equipped with a unary operation ^*: S ï S , called star, satisfying the sum star and product star equations. An iteration semiring is a Conway semiring satisfying Conway's group equations. In this extended abstract, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Fundamenta Informaticae

Fundamenta Informaticae Volume 86, Issue 1,2

October 2008

219 pages

ISSN:0169-2968

Issue’s Table of Contents

Publisher

IOS Press

Netherlands

Publication History

Published: 01 April 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kostolányi P(2019)A Unifying Approach to Algebraic Systems Over SemiringsTheory of Computing Systems10.1007/s00224-018-9895-963:3(615-633)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00224-018-9895-9
Ésik ZHajgató T(2014)On the structure of free iteration semiringsJournal of Automata, Languages and Combinatorics10.5555/3173474.317348019:1(57-66)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.5555/3173474.3173480
Abbad HLaugerotte É(2013)Computing weightsProceedings of the 18th international conference on Implementation and Application of Automata10.1007/978-3-642-39274-0_4(24-35)Online publication date: 16-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39274-0_4
Ésik ZHajgató T(2011)Kleene theorem in partial conway theories with applicationsAlgebraic Foundations in Computer Science10.5555/2172429.2172433(72-93)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/2172429.2172433
Ésik Z(2011)Partial conway and iteration semiring-semimodule pairsAlgebraic Foundations in Computer Science10.5555/2172429.2172432(56-71)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/2172429.2172432
Ésik ZKuich W(2011)A unifying Kleene theorem for weighted finite automataRainbow of computer science10.5555/2001113.2001121(76-89)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/2001113.2001121
Bloom SÉsik Z(2009)Axiomatizing rational power series over natural numbersInformation and Computation10.1016/j.ic.2009.02.003207:7(793-811)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1016/j.ic.2009.02.003
Ésik Z(2008)Iteration SemiringsProceedings of the 12th international conference on Developments in Language Theory10.1007/978-3-540-85780-8_1(1-20)Online publication date: 16-Sep-2008
https://dl.acm.org/doi/10.1007/978-3-540-85780-8_1

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents