| Issue |
RAIRO-Theor. Inf. Appl.
Volume 36, Number 2, April/June 2002
Fixed Points in Computer Science (FICS'01)
|
|
|---|---|---|
| Page(s) | 129 - 153 | |
| DOI | https://doi.org/10.1051/ita:2002007 | |
| Published online | 15 December 2002 | |
A Fully Equational Proof of Parikh's Theorem
1
(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.
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.