Article contents
A Finite Axiomatization of Nondeterministic Regular Expressions
Published online by Cambridge University Press: 15 August 2002
Abstract
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 +.
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 33 , Issue 4-5 , July 1999 , pp. 447 - 465
- Copyright
- © EDP Sciences, 1999
References
- 4
- Cited by