Displaying similar documents to “On the expressive power of the shuffle operator matched with intersection by regular sets”

Consensual languages and matching finite-state computations

Stefano Crespi Reghizzi, Pierluigi San Pietro (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

An ever present, common sense idea in language modelling research is that, for a word to be a valid phrase, it should comply with multiple constraints at once. A new language definition model is studied, based on agreement or consensus between similar strings. Considering a regular set of strings over a bipartite alphabet made by pairs of unmarked/marked symbols, a match relation is introduced, in order to specify when such strings agree. Then a regular set over the bipartite alphabet...

Consensual languages and matching finite-state computations

Stefano Crespi Reghizzi, Pierluigi San Pietro (2011)

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

Similarity:

An ever present, common sense idea in language modelling research is that, for a word to be a valid phrase, it should comply with multiple constraints at once. A new language definition model is studied, based on agreement or consensus between similar strings. Considering a regular set of strings over a bipartite alphabet made by pairs of unmarked/marked symbols, a match relation is introduced, in order to specify when such strings agree. Then a regular set over the bipartite alphabet...

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

C++ Tools to construct our user-level language

Frédéric Hecht (2010)

ESAIM: Mathematical Modelling and Numerical Analysis

Similarity:

The aim of this paper is to present how to make a dedicaded computed language polymorphic and multi type, in to solve partial differential equations with the finite element method. The driving idea is to make the language as close as possible to the mathematical notation.

Polynomial languages with finite antidictionaries

Arseny M. Shur (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.

Classes of two-dimensional languages and recognizability conditions

Marcella Anselmo, Maria Madonia (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

The paper deals with some classes of two-dimensional recognizable languages of “high complexity”, in a sense specified in the paper and motivated by some necessary conditions holding for recognizable and unambiguous languages. For such classes we can solve some open questions related to unambiguity, finite ambiguity and complementation. Then we reformulate a necessary condition for recognizability stated by Matz, introducing a new complexity function. We solve an open question proposed...