A Fully Equational Proof of Parikh's Theorem
Luca Aceto; Zoltán Ésik; Anna Ingólfsdóttir
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 36, Issue: 2, page 129-153
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topAceto, Luca, Ésik, Zoltán, and Ingólfsdóttir, Anna. "A Fully Equational Proof of Parikh's Theorem." RAIRO - Theoretical Informatics and Applications 36.2 (2010): 129-153. <http://eudml.org/doc/92694>.
@article{Aceto2010,
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.
},
author = {Aceto, Luca, Ésik, Zoltán, Ingólfsdóttir, Anna},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Parikh's theorem; commutative context-free languages;
commutative rational languages; equational logic; varieties;
complete axiomatizations; commutative idempotent semirings;
algebraically complete commutative idempotent semi rings.; complete axiomatizations; Parikh vector; context-free language},
language = {eng},
month = {3},
number = {2},
pages = {129-153},
publisher = {EDP Sciences},
title = {A Fully Equational Proof of Parikh's Theorem},
url = {http://eudml.org/doc/92694},
volume = {36},
year = {2010},
}
TY - JOUR
AU - Aceto, Luca
AU - Ésik, Zoltán
AU - Ingólfsdóttir, Anna
TI - A Fully Equational Proof of Parikh's Theorem
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 36
IS - 2
SP - 129
EP - 153
AB -
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.
LA - eng
KW - Parikh's theorem; commutative context-free languages;
commutative rational languages; equational logic; varieties;
complete axiomatizations; commutative idempotent semirings;
algebraically complete commutative idempotent semi rings.; complete axiomatizations; Parikh vector; context-free language
UR - http://eudml.org/doc/92694
ER -
References
top- H. Bekic, Definable operations in general algebras, and the theory of automata and flowcharts, Technical Report. IBM Laboratory, Vienna (1969).
- S.L. Bloom and Z. Ésik, Floyd-Hoare logic in iteration theories. J. Assoc. Comput. Mach.38 (1991) 887-934.
- 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.
- S.L. Bloom and Z. Ésik, Iteration Theories. Springer-Verlag (1993).
- S. Bozapalidis, Equational elements in additive algebras. Theory Comput. Syst.32 (1999) 1-33.
- 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).
- Z. Ésik, Group axioms for iteration. Inform. and Comput.148 (1999) 131-180.
- 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.
- D.T. Huynh, The complexity of semilinear sets. Elektron. Informationsverarb. Kybernet18 (1982) 291-338.
- D.T. Huynh, The complexity of equivalence problems for commutative grammars. Inform. and Control66 (1985) 103-121.
- D. Kozen, A completeness theorem for Kleene algebras and the algebra of regular events. Inform. and Comput.110 (1994) 366-390.
- 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.
- D. Krob, Complete systems of B-rational identities. Theoret. Comput. Sci.89 (1991) 207-343.
- 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.
- R.J. Parikh, On context-free languages. J. Assoc. Comput. Mach.13 (1966) 570-581.
- D.M.R. Park, Fixed point induction and proofs of program properties, in Machine Intelligence, Vol. 5. Edinburgh Univ. Press (1970) 59-78.
- D.L. Pilling, Commutative regular equations and Parikh's theorem. J. London Math. Soc.6 (1973) 663-666.
- 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).
- I. Takanami and N. Honda, A characterization of Parikh's theorem and semilinear sets by commutative semigroups with length. Electron. Comm. Japan52 (1969) 179-184.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.