| Issue |
RAIRO-Theor. Inf. Appl.
Volume 33, Number 4-5, July October 1999
|
|
|---|---|---|
| Page(s) | 447 - 465 | |
| DOI | https://doi.org/10.1051/ita:1999127 | |
| Published online | 15 August 2002 | |
A Finite Axiomatization of Nondeterministic Regular Expressions
1
Università dell'Aquila,
Dipartimento di Matematica Pura ed Applicata, Via Vetoio, Loc. Coppito,
I-67100 L'Aquila, Italy; flavio@univaq.it.
2
Università di Firenze,
Dipartimento di Sistemi e Informatica, Via C. Lombroso 6/17, 50134
Firenze, Italy; denicola@dsi.unifi.it.
3
Università di Roma “La Sapienza”,
Dipartimento di Scienze dell'Informazione, Via Salaria 113, 00198 Roma,
Italy; labella@dsi.uniroma1.it.
Received:
30
November
1998
Revised:
10
June
1999
An alternative (tree-based) semantics for a class of regular expressions is proposed that assigns a central rôle to the + operator and thus to nondeterminism and nondeterministic choice. For the new semantics a consistent and complete axiomatization is obtained from the original axiomatization of regular expressions by Salomaa and by Kozen by dropping the idempotence law for + and the distribution law of • over +.
Mathematics Subject Classification: 68Q55 / 68Q68 / 08B05
Key words: Semantics / regular expressions / axiomatizations / bisimulation.
© EDP Sciences, 1999
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.