Equality sets for recursively enumerable languages

Vesa Halava; Tero Harju; Hendrik Jan Hoogeboom; Michel Latteux

Displaying similar documents to “Equality sets for recursively enumerable languages”

On the expressive power of the shuffle operator matched with intersection by regular sets

Joanna Jȩdrzejowicz, Andrzej Szepietowski (2001)

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

Similarity:

We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form $L \cap R$ , with a shuffle language $L$ and a regular language $R$ , contains non-semilinear languages and does not form a family of mildly context- sensitive languages. ...

Efficiency of automata in semi-commutation verification techniques

Gérard Cécé, Pierre-Cyrille Héam, Yann Mainier (2008)

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

Similarity:

Computing the image of a regular language by the transitive closure of a relation is a central question in regular model checking. In a recent paper Bouajjani et al. [IEEE Comput. Soc. (2001) 399–408] proved that the class of regular languages $L$ – called APC – of the form $\cup_{j}$ $L_{0, j}$ $L_{1, j}$ $L_{2, j}$ $...$ $L_{k_{j}, j}$ , where the union is finite and each $L_{i, j}$ is either a single symbol or a language of the form $B^{*}$ with $B$ a subset of the alphabet, is...

Watson-Crick pushdown automata

Kingshuk Chatterjee, Kumar S. Ray (2017)

Kybernetika

Similarity:

A multi-head 1-way pushdown automaton with $k$ heads is a pushdown automaton with $k$ 1-way read heads on the input tape and a stack. It was previously shown that the deterministic variant of the model cannot accept all the context free languages. In this paper, we introduce a 2-tape, 2-head model namely Watson-Crick pushdown automata where the content of the second tape is determined using a complementarity relation, similar to Watson-Crick automata. We show computational powers of nondeterministic...

On simple representations of language families

K. Culik II, H. A. Maurer (1979)

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

Similarity:

Algebraic caractérisations of NTIME $(F)$ and NTIME $(F, A)$

Hans-Jürgen Stenger (1984)

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

Similarity:

Fair expressions and regular languages over lists

L. Breveglieri (1997)

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

Similarity:

On languages satisfying “interchange Lemma”

Victor Mitrana (1993)

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

Similarity:

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