A Fully Equational Proof of Parikh's Theorem

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

June 2001


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

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.