𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Nondeterministic regular expressions as solutions of equational systems

✍ Scribed by Rocco De Nicola; Anna Labella

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
211 KB
Volume
302
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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, and show that any regular expression can be obtained as a canonical solution of a system of the deΓΏned class.

πŸ“œ SIMILAR VOLUMES

Models of Nondeterministic Regular Expre
Models of Nondeterministic Regular Expressions
✍ Flavio Corradini; Rocco De Nicola; Anna Labella πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 350 KB

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 la

Describing non-deterministic reactive sy
Describing non-deterministic reactive systems by means of regular expressions
✍ Pascal Raymond; Yvan Roux πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 445 KB

This paper presents a language based on regular expressions for describing nondeterministic reactive systems. It also presents some ideas on how to build (or adapt) tools for exploiting such a language (recognizers, generators and provers).

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

Regular Solutions of the Shabat Equation
Regular Solutions of the Shabat Equation
✍ Yunkang Liu πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 286 KB

The Shabat equation where + and q are parameters, is the simplest self-similar reduction of the so-called dressing chain for constructing and analyzing exactly solvable Schro dinger equations. It is so relevant to the study of the q-oscillator algebra in quantum mechanics. The main objective of thi