Displaying similar documents to “Some closure properties of the nondeterministic regular translations.”

A Finite Axiomatization of Nondeterministic Regular Expressions

Flavio Corradini, Rocco De Nicola, Anna Labella (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

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 +.

Conditional Lindenmayer systems with subregular conditions: The non-extended case

Jürgen Dassow, Stefan Rudolf (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We consider conditional tabled Lindenmayer sytems without interaction, where each table is associated with a regular set and a table can only be applied to a sentential form which is contained in its associated regular set. We study the effect to the generative power, if we use instead of arbitrary regular languages only finite, nilpotent, monoidal, combinational, definite, ordered, union-free, star-free, strictly locally testable, commutative regular, circular regular, and suffix-closed...

Extending regular expressions with homomorphic replacement

Henning Bordihn, Jürgen Dassow, Markus Holzer (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We define H- and EH-expressions as extensions of regular expressions by adding homomorphic and iterated homomorphic replacement as new operations, resp. The definition is analogous to the extension given by Gruska in order to characterize context-free languages. We compare the families of languages obtained by these extensions with the families of regular, linear context-free, context-free, and EDT0L languages. Moreover, relations to language families based on patterns, multi-patterns,...