Issue Theoret. Informatics Appl. Volume 36, Number 2, April-June 2002 Fixed Points in Computer Science (FICS'01) Page(s) 129 - 153 DOI 10.1051/ita:2002007

Theoret. Informatics Appl. 36, 129-153 (2002)
DOI: 10.1051/ita:2002007

A Fully Equational Proof of Parikh's Theorem

Luca Aceto¹, Zoltán Ésik² and Anna Ingólfsdóttir<sup>1

1</sup>  BRICS (Basic R esearch in Computer Science, Centre of the Danish National Research Foundation), Department of Computer Science, Aalborg University, Fr. Bajersvej 7E, 9220 Aalborg Ø, Denmark; luca@cs.auc.dk.
²  Department of Computer Science, University of Szeged, P.O. Box 652, 6701 Szeged, Hungary.

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 -term equations of continuous commutative idempotent semirings.

Mathematics Subject Classification. 03C05, 16Y60, 68Q70

Key words: Parikh's theorem -- commutative context-free languages -- commutative rational languages -- equational logic -- varieties -- complete axiomatizations -- commutative idempotent semirings -- algebraically complete commutative idempotent semi rings.


© EDP Sciences 2002

What is OpenURL?