Abstract
We give inequational and equational axioms for semirings with a fixed-point operator and formally develop a fragment of the theory of context-free languages. In particular, we show that Greibach’s normal form theorem depends only on a few equational properties of least pre-fixed-points in semirings, and elimination of chain- and deletion rules depend on their inequational properties (and the idempotency of addition). It follows that these normal form theorems also hold in non-continuous semirings having enough fixed-points.
This author was supported by BRICS (Aalborg) and the National Foundation of Hungary for Scientific Research, grant T35169.
This author was supported by a travel grant from the Humboldt-Foundation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Aceto, Z. Ésik and A. Ingólfsdóttir. A fully equational proof of Parikh’s theorem. BRICS Report Series, RS-01-28, Aarhus, 2001.
J. W. de Bakker and D. Scott. A theory of programs. IBM Seminar, August, 1969.
H. Bekić. Definable operations in general algebra, and the theory of automata and flowcharts. Technical Report, IBM Laboratory, Vienna, 1969.
L. Bernátsky, S. L. Bloom, Z. Ésik, and Gh. Stefanescu. Equational theories of relations and regular sets, extended abstract. In Proceedings of the Conference on Words, Combinatorics and Semigroups,Kyoto, 1992, pages 40–48. World Scientific Publishing Co. Pte. Ltd., 1994.
S. L. Bloom and Z. Ésik. Iteration algebras, Int. J. Foundations of Computer Science, 3(1991), 245–302.
S.L. Bloom and Z. Ésik. Iteration Theories, Springer, 1993.
M. Boffa. Une condition impliquant toutes les identités rationnelles. RAIRO Inform. Théor. Appl., 29 (1995), 515–518.
J. H. Conway. Regular Algebra and Finite Machines. Chapman and Hall, London, 1971.
Z. Ésik. Completeness of Park induction, Theoretical Computer Science, 177 (1997), 217–283.
Z. Ésik and W. Kuich. Inductive *-semirings. To appear in Theoretical Computer Science.
S.A. Greibach. A new normal-form theorem for context-free, phrase-structure grammars. J. of the Association for Computing Machinery, 12 (1965), 42–52.
M. Harrison. Introduction to Formal Languages. Addison Wesley, Reading, 1978.
M. W. Hopkins and D. Kozen. Parikh’s theorem in commutative Kleene algebra. In Proc. Symp. Logic in Computer Science (LICS’99), IEEE Press, 1999, 394–401.
D. Kozen. A completeness theorem for Kleene algebras and the algebra of regular events. In 6th Ann. Symp. on Logic in Computer Science, LICS’91. Computer Society Press, 1991, 214–225.
D. Kozen. On the complexity of reasoning in Kleene algebra. In Proc. 12th Symp. Logic in Computer Science, IEEE Press, 1997, 195–202.
D. Krob. Complete systems of B-rational identities. Theoret. Comput. Sci., 89 (1991), 207–343.
H. Leiβ. Towards Kleene Algebra with Recursion. In Proc. 5th Workshop on Computer Science Logic, CSL’ 91. Springer LNCS 626, 242–256, 1991.
K. C. Ng and A. Tarski. Relation algebras with transitive closure. Notices of the American Math. Society, 24:A29–A30, 1977.
D. Niwinski. Equational µ-calculus. In Computation Theory (Zaborow, 1984), pages 169–176, Springer LNCS 208, 1984.
V. R. Pratt. Action Logic and Pure Induction. In Logics in AI: European Workshop JELIA’ 90. Springer LNCS 478, 97–120, 1990.
V. N. Redko. On the determining totality of relations for the algebra of regular events. (Russian) Ukrain. Mat. Ž., 16 (1964), 120–126.
D.J. Rosenkrantz. Matrix equations and normal forms for context-free grammars. Journal of the Association for Computing Machinery, 14 (1967), 501–507.
A. Salomaa. Two complete axiom systems for the algebra of regular events. Journal of the Association for Computing Machinery, 13 (1966), 158–169.
L. Santocanale. On the equational definition of the least prefixed point. In MFCS 2001, pages 645–656, Springer LNCS 2136, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ésik, Z., Leiβ, H. (2002). Greibach Normal Form in Algebraically Complete Semirings. In: Bradfield, J. (eds) Computer Science Logic. CSL 2002. Lecture Notes in Computer Science, vol 2471. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45793-3_10
Download citation
DOI: https://doi.org/10.1007/3-540-45793-3_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44240-0
Online ISBN: 978-3-540-45793-0
eBook Packages: Springer Book Archive