𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Models of Nondeterministic Regular Expressions

✍ Scribed by Flavio Corradini; Rocco De Nicola; Anna Labella

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
350 KB
Volume
59
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

Nondeterminism is a direct outcome of interactions and is, therefore a central ingredient for modelling concurrent systems. Trees are very useful for modelling nondeterministic behaviour. We aim at a tree-based interpretation of regular expressions and study the effect of removing the idempotence law X+X=X and the distribution law X v (Y+Z)=X vY+X vZ from Kleene algebras. We show that the free model of the new set of axioms is a class of trees labelled over A. We also equip regular expressions with a two-level behavioural semantics. The basic level is described in terms of a class of labelled transition systems that are detailed enough to describe the number of equal actions a system can perform from a given state. The abstract level is based on a so-called resource bisimulation preorder that permits ignoring uninteresting details of transition systems. The three proposed interpretations of regular expressions (algebraic, denotational, and behavioural ) are proven to coincide. When dealing with infinite behaviours, we rely on a simple version of the |-induction and obtain a complete proof system also for the full language of nondeterministic regular expressions.

πŸ“œ SIMILAR VOLUMES

Nondeterministic regular expressions as
Nondeterministic regular expressions as solutions of equational systems
✍ Rocco De Nicola; Anna Labella πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 211 KB

We deΓΏne the class of the linear systems whose solution is expressible as a tuple of nondeterministic regular expressions when they are interpreted as trees of actions rather than as sets of sequences. We precisely characterize those systems that have a regular expression as "canonical" solution, an

Translating Regular Expressions into Sma
Translating Regular Expressions into Small Ξ΅-Free Nondeterministic Finite Automata
✍ Juraj Hromkovič; Sebastian Seibert; Thomas Wilke πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 252 KB

We prove that every regular expression of size n can be converted into an equivalent nondeterministic =-free finite automaton (NFA) with O(n(log n) 2 ) transitions in time O(n 2 log n). The best previously known conversions result in NFAs of worst-case size 3(n 2 ). We complement our result by provi

Rewriting of Regular Expressions and Reg
Rewriting of Regular Expressions and Regular Path Queries
✍ Diego Calvanese; Giuseppe De Giacomo; Maurizio Lenzerini; Moshe Y. Vardi πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 189 KB

Recent work on semi-structured data has revitalized the interest in path queries, i.e., queries that ask for all pairs of objects in the database that are connected by a path conforming to a certain specification, in particular to a regular expression. Also, in semi-structured data, as well as in da

Translation of binary regular expression
Translation of binary regular expressions into nondeterministic Ξ΅-free automata with O(n log n) transitions
✍ Viliam Geffert πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 281 KB

We show that every regular expression of size n over a fixed alphabet of s symbols can be converted into a nondeterministic e-free finite-state automaton with Oðsn log nÞ transitions (edges). In case of binary regular languages, this improves the previous known conversion from Oðnðlog nÞ 2 Þ transit