A Fully Equational Proof of Parikh's Theorem

Authors

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

DOI:

https://doi.org/10.7146/brics.v8i28.21688

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.

Downloads

Published

2001-06-04

How to Cite

Aceto, L., Ésik, Z., & Ingólfsdóttir, A. (2001). A Fully Equational Proof of Parikh’s Theorem. BRICS Report Series, 8(28). https://doi.org/10.7146/brics.v8i28.21688