A Fully Equational Proof of Parikh's Theorem
(asic esearch in omputer cience, Centre of the Danish
National Research Foundation),
Department of Computer Science, Aalborg University,
Fr. Bajersvej 7E, 9220 Aalborg Ø, Denmark;
2 Department of Computer Science, University of Szeged, P.O. Box 652, 6701 Szeged, Hungary.
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