A finite axiomatization of nondeterministic regular expressions

Authors
Corradini, F De Nicola, R Labella, A
Citation
F. Corradini et al., A finite axiomatization of nondeterministic regular expressions, RAIRO-INF, 33(4-5), 1999, pp. 447-465
Citations number
34
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS
ISSN journal
09883754 → ACNP
Volume
33
Issue
4-5
Year of publication
1999
Pages
447 - 465
Database
ISI
SICI code
0988-3754(199907/10)33:4-5<447:AFAONR>2.0.ZU;2-I
Abstract
An alternative (tree-based) semantics for a dass of regular expressions is proposed that assigns a central role to the + operator and thus to nondeter minism and nondeterministic choice. For the new semantics a consistent and complete axiomatization is obtained from the original axiomatization of reg ular expressions by Salomaa and by Kozen by dropping the idempotence law fo r + and the distribution law of . over +. AMS Subject Classification. 68Q55 , 68Q68, 08B05.