A Fully Equational Proof of Parikh's Theorem
Aceto, Luca; Ésik, Zoltán; Ingólfsdóttir, Anna; Aceto Luca; (asic esearch in omputer cience, Centre of the Danish National Research Foundation), Department of Computer Science, Aalborg University, Fr. Bajersvej 7E, 9220 Aalborg Ø, Denmark; luca@cs.auc.dk.; Ésik Zoltán; Department of Computer Science, University of Szeged, P.O. Box 652, 6701 Szeged, Hungary.; Ingólfsdóttir Anna; (asic esearch in omputer cience, Centre of the Danish National Research Foundation), Department of Computer Science, Aalborg University, Fr. Bajersvej 7E, 9220 Aalborg Ø, Denmark; luca@cs.auc.dk.
Журнал:
RAIRO - Theoretical Informatics and Applications
Дата:
2002
Аннотация:
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.
195.6Кб