Abstract
In Kuich [4] we generalized the Kleene and the Parikh Theorem to l-complete semirings whose natural limit function is compatible with their partial order. In this paper we generalize in the same manner the following language theoretic result: A language is context-free iff it is accepted by a pushdown automaton.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Goldstern, M.: Vervollständigung von Halbringen. Diplomarbeit Technische Universität Wien, 1985.
Hebisch, U.: Zur algebraischen Theorie unendlicher Summen in Halbgruppen und Halbringen. Habilitationsschrift Technische Universität Clausthal, 1990.
Karner, G.: On limits in complete semirings. Manuscript Technische Universität Wien, 1990.
Kuich, W.: The Kleene and the Parikh Theorem in complete semirings. ICALP 1987, LNCS 267 (1987), 212–225.
Kuich, W., Salomaa, A.: Semirings, Automata, Languages. Springer, 1986.
Lausch, H., Nöbauer, W.: Algebra of Polynomials. North-Holland, 1973.
Loeckx, J., Sieber, K.: The Foundations of Program Verification. Wiley-Teubner, 1984.
Sakarovitch, J.: Kleene's Theorem revisited. LNCS 281 (1987), 39–50.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kuich, W. (1990). ω-Continuous semirings, algebraic systems and pushdown automata. In: Paterson, M.S. (eds) Automata, Languages and Programming. ICALP 1990. Lecture Notes in Computer Science, vol 443. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0032025
Download citation
DOI: https://doi.org/10.1007/BFb0032025
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-52826-5
Online ISBN: 978-3-540-47159-2
eBook Packages: Springer Book Archive