A Finite Axiomatization of Nondeterministic Regular Expressions
Corradini, Flavio; De Nicola, Rocco; Labella, Anna; Corradini Flavio; Università dell'Aquila, Dipartimento di Matematica Pura ed Applicata, Via Vetoio, Loc. Coppito, I-67100 L'Aquila, Italy; flavio@univaq.it.; De Nicola Rocco; Università di Firenze, Dipartimento di Sistemi e Informatica, Via C. Lombroso 6/17, 50134 Firenze, Italy; denicola@dsi.unifi.it.; Labella Anna; Università di Roma “La Sapienza”, Dipartimento di Scienze dell'Informazione, Via Salaria 113, 00198 Roma, Italy; labella@dsi.uniroma1.it.
Журнал:
RAIRO - Theoretical Informatics and Applications
Дата:
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 +.
194.0Кб