Set-theoretical operations on -multiple languages
Jaroslav Král (1967)
Kybernetika
Similarity:
Jaroslav Král (1967)
Kybernetika
Similarity:
Patrizio Cintioli, Riccardo Silvestri (2001)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Schöning [14] introduced a notion of helping and suggested the study of the class of the languages that can be helped by oracles in a given class . Later, Ko [12], in order to study the connections between helping and “witness searching”, introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call which contains all the self-helping classes. We introduce the Helping hierarchy whose...
Alexander Okhotin (2004)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et 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...
Branislav Rovan (1969)
Kybernetika
Similarity:
Viliam Geffert, L'ubomíra Ištoňová (2010)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with nested pebbles....