Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-24T02:05:51.851Z Has data issue: false hasContentIssue false
  • English
  • Français

A Fully Equational Proof of Parikh's Theorem

Published online by Cambridge University Press:  15 December 2002

Luca Aceto ,
Zoltán Ésik  and
Anna Ingólfsdóttir
Luca Aceto
Affiliation:
(asic esearch in omputer cience, Centre of the Danish National Research Foundation), Department of Computer Science, Aalborg University, Fr. Bajersvej 7E, 9220 Aalborg Ø, Denmark; [email protected].
Zoltán Ésik
Affiliation:
Department of Computer Science, University of Szeged, P.O. Box 652, 6701 Szeged, Hungary.
Anna Ingólfsdóttir
Affiliation:
(asic esearch in omputer cience, Centre of the Danish National Research Foundation), Department of Computer Science, Aalborg University, Fr. Bajersvej 7E, 9220 Aalborg Ø, Denmark; [email protected].
Get access

Abstract

We show that the validity of Parikh's theorem for context-free languages depends only on a few equational properties of least pre-fixed points. Moreover, we exhibit an infinite basis of μ-term equations of continuous commutative idempotent semirings.

Keywords

Parikh's theoremcommutative context-free languagescommutative rational languagesequational logicvarietiescomplete axiomatizationscommutative idempotent semiringsalgebraically complete commutative idempotent semi rings.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 36 , Issue 2: Fixed Points in Computer Science (FICS'01) , April 2002 , pp. 129 - 153
Copyright
© EDP Sciences, 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

H. Bekic, Definable operations in general algebras, and the theory of automata and flowcharts, Technical Report. IBM Laboratory, Vienna (1969).
Bloom, S.L. and Ésik, Z., Floyd-Hoare logic in iteration theories. J. Assoc. Comput. Mach. 38 (1991) 887-934. CrossRef
S.L. Bloom and Z. Ésik, Program correctness and matricial iteration theories, in Proc. Mathematical Foundations of Programming Semantics'91. Springer-Verlag, Lecture Notes in Comput. Sci. 598 (1992) 457-475. CrossRef
S.L. Bloom and Z. Ésik, Iteration Theories. Springer-Verlag (1993).
Bozapalidis, S., Equational elements in additive algebras. Theory Comput. Syst. 32 (1999) 1-33. CrossRef
J. Conway, Regular Algebra and Finite Machines. Chapman and Hall (1971).
J.W. De Bakker and D. Scott, A theory of programs, in IBM Seminar. Vienna (1969).
Ésik, Z., Group axioms for iteration. Inform. and Comput. 148 (1999) 131-180. CrossRef
Z. Ésik and H. Leiss, Greibach normal form in algebraically complete semirings, in Proc. Annual Conference of the European Association for Computer Science Logic, CSL'02. Springer, Lecture Notes in Comput. Sci. (to appear).
S. Ginsburg, The Mathematical Theory of Context-Free Languages. McGraw-Hill (1966).
A. Ginzburg, Algebraic Theory of Automata. Academic Press, New York-London (1968).
J.S. Golan, Semirings and their Applications. Kluwer Academic Publishers, Dordrecht (1999).
J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass. (1979).
M.W. Hopkins and D. Kozen, Parikh's theorem in commutative Kleene algebra, in Proc. IEEE Conf. Logic in Computer Science (LICS'99). IEEE Press (1999) 394-401.
Huynh, D.T., The complexity of semilinear sets. Elektron. Informationsverarb. Kybernet 18 (1982) 291-338.
Huynh, D.T., The complexity of equivalence problems for commutative grammars. Inform. and Control 66 (1985) 103-121. CrossRef
Kozen, D., A completeness theorem for Kleene algebras and the algebra of regular events. Inform. and Comput. 110 (1994) 366-390. CrossRef
D. Kozen, On Hoare logic and Kleene algebra with tests, in Proc. IEEE Conf. Logic in Computer Science (LICS'99). IEEE Press (1999) 167-172.
Krob, D., Complete systems of B-rational identities. Theoret. Comput. Sci. 89 (1991) 207-343. CrossRef
W. Kuich, The Kleene and the Parikh theorem in complete semirings, in Proc. ICALP '87. Springer-Verlag, Lecture Notes in Comput. Sci. 267 (1987) 212-225.
W. Kuich, Gaussian elimination and a characterization of algebraic power series, in Proc. Mathematical Foundations of Computer Science, 1998. Springer, Berlin, Lecture Notes in Comput. Sci. 1450 (1998) 512-521.
W. Kuich and A. Salomaa, Semirings, Automata, Languages. Springer-Verlag, Berlin (1986).
E.G. Manes and M.A. Arbib, Algebraic Approaches to Program Semantics. Springer-Verlag, New York (1986).
D. Niwinski, On fixed-point clones (extended abstract), in Automata, Languages and Programming, Rennes, 1986. Springer, Lecture Notes in Comput. Sci. 226 (1986) 464-473.
Parikh, R.J., On context-free languages. J. Assoc. Comput. Mach. 13 (1966) 570-581. CrossRef
D.M.R. Park, Fixed point induction and proofs of program properties, in Machine Intelligence, Vol. 5. Edinburgh Univ. Press (1970) 59-78.
Pilling, D.L., Commutative regular equations and Parikh's theorem. J. London Math. Soc. 6 (1973) 663-666. CrossRef
V.N. Redko, On the algebra of commutative events. (Russian) Ukrain. Mat. Z. 16 (1964) 185-195.
A. Salomaa, Theory of Automata. Pergamon Press (1969).
Takanami, I. and Honda, N., A characterization of Parikh's theorem and semilinear sets by commutative semigroups with length. Electron. Comm. Japan 52 (1969) 179-184.