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 theorem, commutative context-free languages, commutative rational languages, equational logic, varieties, complete axiomatizations, commutative idempotent semirings, algebraically complete commutative idempotent semirings
@article{ITA_2002__36_2_129_0,
author = {Aceto, Luca and \'Esik, Zolt\'an and Ing\'olfsd\'ottir, Anna},
title = {A fully equational proof of {Parikh's} theorem},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {129--153},
year = {2002},
publisher = {EDP Sciences},
volume = {36},
number = {2},
doi = {10.1051/ita:2002007},
zbl = {1024.68070},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ita:2002007/}
}
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 - Informatique Théorique et Applications PY - 2002 SP - 129 EP - 153 VL - 36 IS - 2 PB - EDP Sciences UR - https://www.numdam.org/articles/10.1051/ita:2002007/ DO - 10.1051/ita:2002007 LA - en ID - ITA_2002__36_2_129_0 ER -
%0 Journal Article %A Aceto, Luca %A Ésik, Zoltán %A Ingólfsdóttir, Anna %T A fully equational proof of Parikh's theorem %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2002 %P 129-153 %V 36 %N 2 %I EDP Sciences %U https://www.numdam.org/articles/10.1051/ita:2002007/ %R 10.1051/ita:2002007 %G en %F ITA_2002__36_2_129_0
Aceto, Luca; Ésik, Zoltán; Ingólfsdóttir, Anna. A fully equational proof of Parikh's theorem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 2, pp. 129-153. doi: 10.1051/ita:2002007
[1] , Definable operations in general algebras, and the theory of automata and flowcharts, Technical Report. IBM Laboratory, Vienna (1969).
[2] and, Floyd-Hoare logic in iteration theories. J. Assoc. Comput. Mach. 38 (1991) 887-934. | Zbl | MR
[3] and, 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.
[4] and, Iteration Theories. Springer-Verlag (1993). | Zbl | MR
[5] , Equational elements in additive algebras. Theory Comput. Syst. 32 (1999) 1-33. | Zbl | MR
[6] , Regular Algebra and Finite Machines. Chapman and Hall (1971). | Zbl
[7] and, A theory of programs, in IBM Seminar. Vienna (1969).
[8] , Group axioms for iteration. Inform. and Comput. 148 (1999) 131-180. | Zbl | MR
[9] and, 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). | Zbl
[10] , The Mathematical Theory of Context-Free Languages. McGraw-Hill (1966). | Zbl | MR
[11] , Algebraic Theory of Automata. Academic Press, New York-London (1968). | Zbl | MR
[12] , Semirings and their Applications. Kluwer Academic Publishers, Dordrecht (1999). | Zbl | MR
[13] and, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass. (1979). | Zbl | MR
[14] and, Parikh's theorem in commutative Kleene algebra, in Proc. IEEE Conf. Logic in Computer Science (LICS'99). IEEE Press (1999) 394-401.
[15] , The complexity of semilinear sets. Elektron. Informationsverarb. Kybernet 18 (1982) 291-338. | Zbl | MR
[16] , The complexity of equivalence problems for commutative grammars. Inform. and Control 66 (1985) 103-121. | Zbl | MR
[17] , A completeness theorem for Kleene algebras and the algebra of regular events. Inform. and Comput. 110 (1994) 366-390. | Zbl | MR
[18] , On Hoare logic and Kleene algebra with tests, in Proc. IEEE Conf. Logic in Computer Science (LICS'99). IEEE Press (1999) 167-172.
[19] , Complete systems of -rational identities. Theoret. Comput. Sci. 89 (1991) 207-343. | Zbl | MR
[20] , The Kleene and the Parikh theorem in complete semirings, in Proc. ICALP '87. Springer-Verlag, Lecture Notes in Comput. Sci. 267 (1987) 212-225. | Zbl
[21] , 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. | Zbl | MR
[22] and, Semirings, Automata, Languages. Springer-Verlag, Berlin (1986). | Zbl | MR
[23] and, Algebraic Approaches to Program Semantics. Springer-Verlag, New York (1986). | Zbl | MR
[24] , On fixed-point clones (extended abstract), in Automata, Languages and Programming, Rennes, 1986. Springer, Lecture Notes in Comput. Sci. 226 (1986) 464-473. | Zbl | MR
[25] , On context-free languages. J. Assoc. Comput. Mach. 13 (1966) 570-581. | Zbl | MR
[26] , Fixed point induction and proofs of program properties, in Machine Intelligence, Vol. 5. Edinburgh Univ. Press (1970) 59-78. | Zbl
[27] , Commutative regular equations and Parikh's theorem. J. London Math. Soc. 6 (1973) 663-666. | Zbl
[28] , On the algebra of commutative events. (Russian) Ukrain. Mat. Ž. 16 (1964) 185-195. | MR
[29] , Theory of Automata. Pergamon Press (1969). | Zbl | MR
[30] and, A characterization of Parikh's theorem and semilinear sets by commutative semigroups with length. Electron. Comm. Japan 52 (1969) 179-184.
Cité par Sources :
