Watson-Crick pushdown automata

Kingshuk Chatterjee; Kumar S. Ray

Displaying similar documents to “Watson-Crick pushdown automata”

Embedding odometers in cellular automata

Ethan M. Coven, Reem Yassawi (2009)

Fundamenta Mathematicae

Similarity:

We consider the problem of embedding odometers in one-dimensional cellular automata. We show that (1) every odometer can be embedded in a gliders-with-reflecting-walls cellular automaton, which one depending on the odometer, and (2) an odometer can be embedded in a cellular automaton with local rule $x_{i} \mapsto x_{i} + x_{i + 1} m o d n$ (i ∈ ℤ), where n depends on the odometer, if and only if it is “finitary.”

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

Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata

Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini (2001)

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

Similarity:

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family ${L_{m}}$ of cyclic languages, where $L_{m} = {a^{k m} | k \in ℕ}$ . In particular, we show that, for any $m$ , the number of states necessary and sufficient for accepting the unary language $L_{m}$ with isolated cut point on one-way probabilistic finite automata is $p_{1}^{α_{1}} + p_{2}^{α_{2}} + \dots + p_{s}^{α_{s}}$ , with $p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{s}^{α_{s}}$ being the factorization of $m$ . To prove this result, we give a general state lower bound for accepting unary languages with isolated...

Equality sets for recursively enumerable languages

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux (2005)

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

Similarity:

We consider shifted equality sets of the form $E_{G} (a, g_{1}, g_{2}) = {w ∣ g_{1} (w) = a g_{2} (w)}$ , where $g_{1}$ and $g_{2}$ are nonerasing morphisms and $a$ is a letter. We are interested in the family consisting of the languages $h (E_{G} (J))$ , where $h$ is a coding and $E_{G} (J)$ is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language $L \subseteq A^{*}$ is a projection of a shifted equality set, that is, $L = π_{A} (E_{G} (a, g_{1}, g_{2}))$ for some (nonerasing) morphisms $g_{1}$ and $g_{2}$ and a letter $a$ , where $π_{A}$ deletes the letters not in $A$ . Then...

On the equivalence of linear conjunctive grammars and trellis automata

Alexander Okhotin (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence...