A fully equational proof of Parikh’s theorem

Luca Aceto; Zoltán Ésik; Anna Ingólfsdóttir

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2002)

  • Volume: 36, Issue: 2, page 129-153
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Aceto, Luca, Ésik, Zoltán, and Ingólfsdóttir, Anna. "A fully equational proof of Parikh’s theorem." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 36.2 (2002): 129-153. <http://eudml.org/doc/244701>.

@article{Aceto2002,
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 $\mu $-term equations of continuous commutative idempotent semirings.},
author = {Aceto, Luca, Ésik, Zoltán, Ingólfsdóttir, Anna},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {Parikh’s theorem; commutative context-free languages; commutative rational languages; equational logic; varieties; complete axiomatizations; commutative idempotent semirings; algebraically complete commutative idempotent semirings; Parikh vector; context-free language},
language = {eng},
number = {2},
pages = {129-153},
publisher = {EDP-Sciences},
title = {A fully equational proof of Parikh’s theorem},
url = {http://eudml.org/doc/244701},
volume = {36},
year = {2002},
}

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
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 $\mu $-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 semirings; Parikh vector; context-free language
UR - http://eudml.org/doc/244701
ER -

References

top
  1. [1] H. Bekić, Definable operations in general algebras, and the theory of automata and flowcharts, Technical Report. IBM Laboratory, Vienna (1969). 
  2. [2] S.L. Bloom and Z. Ésik, Floyd-Hoare logic in iteration theories. J. Assoc. Comput. Mach. 38 (1991) 887-934. Zbl0799.68042MR1134520
  3. [3] 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. 
  4. [4] S.L. Bloom and Z. Ésik, Iteration Theories. Springer-Verlag (1993). Zbl0773.03033MR1295433
  5. [5] S. Bozapalidis, Equational elements in additive algebras. Theory Comput. Syst. 32 (1999) 1-33. Zbl0914.68118MR1657328
  6. [6] J. Conway, Regular Algebra and Finite Machines. Chapman and Hall (1971). Zbl0231.94041
  7. [7] J.W. De Bakker and D. Scott, A theory of programs, in IBM Seminar. Vienna (1969). 
  8. [8] Z. Ésik, Group axioms for iteration. Inform. and Comput. 148 (1999) 131-180. Zbl0924.68143MR1674307
  9. [9] 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). Zbl1020.68056
  10. [10] S. Ginsburg, The Mathematical Theory of Context-Free Languages. McGraw-Hill (1966). Zbl0184.28401MR211815
  11. [11] A. Ginzburg, Algebraic Theory of Automata. Academic Press, New York-London (1968). Zbl0195.02501MR242679
  12. [12] J.S. Golan, Semirings and their Applications. Kluwer Academic Publishers, Dordrecht (1999). Zbl0947.16034MR1746739
  13. [13] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass. (1979). Zbl0426.68001MR645539
  14. [14] 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. 
  15. [15] D.T. Huynh, The complexity of semilinear sets. Elektron. Informationsverarb. Kybernet 18 (1982) 291-338. Zbl0519.68060MR703256
  16. [16] D.T. Huynh, The complexity of equivalence problems for commutative grammars. Inform. and Control 66 (1985) 103-121. Zbl0601.68048MR818858
  17. [17] D. Kozen, A completeness theorem for Kleene algebras and the algebra of regular events. Inform. and Comput. 110 (1994) 366-390. Zbl0806.68082MR1276741
  18. [18] 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. 
  19. [19] D. Krob, Complete systems of B -rational identities. Theoret. Comput. Sci. 89 (1991) 207-343. Zbl0737.68053MR1133622
  20. [20] 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. Zbl0625.16026
  21. [21] 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. Zbl0918.68059MR1684095
  22. [22] W. Kuich and A. Salomaa, Semirings, Automata, Languages. Springer-Verlag, Berlin (1986). Zbl0582.68002MR817983
  23. [23] E.G. Manes and M.A. Arbib, Algebraic Approaches to Program Semantics. Springer-Verlag, New York (1986). Zbl0599.68008MR860560
  24. [24] D. Niwiński, On fixed-point clones (extended abstract), in Automata, Languages and Programming, Rennes, 1986. Springer, Lecture Notes in Comput. Sci. 226 (1986) 464-473. Zbl0596.68036MR864709
  25. [25] R.J. Parikh, On context-free languages. J. Assoc. Comput. Mach. 13 (1966) 570-581. Zbl0154.25801MR209093
  26. [26] D.M.R. Park, Fixed point induction and proofs of program properties, in Machine Intelligence, Vol. 5. Edinburgh Univ. Press (1970) 59-78. Zbl0219.68007
  27. [27] D.L. Pilling, Commutative regular equations and Parikh’s theorem. J. London Math. Soc. 6 (1973) 663-666. Zbl0277.68045
  28. [28] V.N. Redko, On the algebra of commutative events. (Russian) Ukrain. Mat. Ž. 16 (1964) 185-195. MR162712
  29. [29] A. Salomaa, Theory of Automata. Pergamon Press (1969). Zbl0193.32901MR262021
  30. [30] I. Takanami and N. Honda, A characterization of Parikh’s theorem and semilinear sets by commutative semigroups with length. Electron. Comm. Japan 52 (1969) 179-184. 

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.