Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T12:18:30.075Z Has data issue: false hasContentIssue false

A Finite Axiomatizationof Nondeterministic Regular Expressions

Published online by Cambridge University Press:  15 August 2002

Flavio Corradini
Affiliation:
Università dell'Aquila, Dipartimento di Matematica Pura ed Applicata, Via Vetoio, Loc. Coppito, I-67100 L'Aquila, Italy; flavio@univaq.it.
Rocco De Nicola
Affiliation:
Università di Firenze, Dipartimento di Sistemi e Informatica, Via C. Lombroso 6/17, 50134 Firenze, Italy; denicola@dsi.unifi.it.
Anna Labella
Affiliation:
Università di Roma “La Sapienza”, Dipartimento di Scienze dell'Informazione, Via Salaria 113, 00198 Roma, Italy; labella@dsi.uniroma1.it.
Get access

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 tonondeterminism and nondeterministic choice. For the new semantics aconsistent 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 +.

Information

Type
Research Article
Copyright
© EDP Sciences, 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable