Reversal-bounded multipushdown machines

DOI10.1016/S0022-0000(74)80027-9zbMath0309.68043MaRDI QIDQ1219160

Publication date: 1974

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Recursively (computably) enumerable sets and degrees (03D25) Turing machines and related notions (03D10)

Related Items

On the complexity of decision problems for some classes of machines and applications ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ Unnamed Item ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS ⋮ ON THE DESCRIPTIONAL COMPLEXITY OF METALINEAR CD GRAMMAR SYSTEMS ⋮ Variations of checking stack automata: obtaining unexpected decidability properties ⋮ FORMAL MODELLING OF VIRAL GENE COMPRESSION ⋮ The effect of end-markers on counter machines and commutativity ⋮ The chop of languages ⋮ The conformon-P system: a molecular and cell biology-inspired computability model ⋮ On the Density of Context-Free and Counter Languages ⋮ An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines ⋮ On the generating power of regularly controlled bidirectional grammars ⋮ Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs ⋮ Simulating one-reversal multicounter machines by partially blind multihead finite automata ⋮ Unnamed Item ⋮ SCHEMA FOR PARALLEL INSERTION AND DELETION: REVISITED ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ On reversal bounded alternating Turing machines ⋮ Pushdown automata with reversal-bounded counters ⋮ On selective unboundedness of VASS ⋮ On some decision questions concerning pushdown machines ⋮ Families of languages defined by ciliate bio-operations ⋮ Information rate of some classes of non-regular languages: an automata-theoretic approach ⋮ Deletion operations on deterministic families of automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the power of 1-tape off-line ATMs running in a bounded number of reversals ⋮ Cônes rationnels commutatifs ⋮ Recursivite et cônes rationnels fermés par intersection ⋮ Similarity in languages and programs ⋮ On linear languages recognized by deterministic biautomata ⋮ On the power of alternation on reversal-bounded alternating Turing machines with a restriction ⋮ Simple counter machines and number-theoretic problems ⋮ Reset machines ⋮ On store languages and applications ⋮ On two-way weak counter machines ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ Insertion operations on deterministic reversal-bounded counter machines ⋮ Unnamed Item ⋮ Multiple equality sets and Post machines ⋮ The complexity of the equivalence problem for two characterizations of Presburger sets ⋮ The complexity of decision problems for finite-turn multicounter machines ⋮ Independance forte de certaines opérations ⋮ On the Density of Context-Free and Counter Languages ⋮ On the complexity and decidability of some problems involving shuffle ⋮ Petri nets and regular languages ⋮ REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS ⋮ On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals ⋮ 2DST mappings of languages and related problems ⋮ Computational power of two stacks with restricted communication ⋮ The difference between one tape and two tapes: With respect to reversal complexity ⋮ Restricted use of the splicing operation¹ ⋮ Closure and decidability properties of some language classes with respect to ciliate bio-operations. ⋮ Refining the hierarchy of blind multicounter languages and twist-closed trios. ⋮ The Computation of Partial Recursive Word‐Functions Without Read Instructions ⋮ The Boolean closure of linear context-free languages ⋮ Quotient and bounded context-free languages ⋮ Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines ⋮ Inclusion is undecidable for pattern languages ⋮ Unnamed Item ⋮ HOW TO SYNCHRONIZE THE HEADS OF A MULTITAPE AUTOMATON ⋮ Further remarks on DNA overlap assembly ⋮ Characterizations of re languages starting from internal contextual languages^∗ ⋮ Accepting runs in a two-way finite automaton ⋮ Unnamed Item ⋮ Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity ⋮ CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES ⋮ Decision problems for language equations ⋮ Undecidability in matrices over Laurent polynomials. ⋮ On partially blind multihead finite automata. ⋮ On the universe, disjointness, and containment problems for simple machines ⋮ Comparing language operations ⋮ One-reversal counter machines and multihead automata: revisited ⋮ Restricted one-counter machines with undecidable universe problems ⋮ Control sets on context-free grammar forms ⋮ On store languages of language acceptors ⋮ One way finite visit automata ⋮ On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs ⋮ Decidability and Shortest Strings in Formal Languages ⋮ Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals ⋮ On a class of languages with holonomic generating functions ⋮ Remarks on blind and partially blind one-way multicounter machines ⋮ On finite-index indexed grammars and their restrictions ⋮ One-Reversal Counter Machines and Multihead Automata: Revisited ⋮ UNSOLVABILITY LEVELS OF OPERATION PROBLEMS FOR SUBCLASSES OF CONTEXT-FREE LANGUAGES ⋮ A technique for proving decidability of containment and equivalence of linear constraint queries ⋮ On characterizations of recursively enumerable languages ⋮ Regular and linear permutation languages ⋮ Some classes of languages in \(NC^ 1\) ⋮ On representing recursively enumerable languages by internal contextual languages ⋮ Equivalence problem for finitely iterated counter machines ⋮ On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L ⋮ Representing recursively enumerable languages by iterated deletion ⋮ On some bounded semiAFLs and AFLs ⋮ On composition and lookahead delegation of \(e\)-services modeled by automata ⋮ SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS ⋮ ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS ⋮ On families of full trios containing counter machine languages ⋮ Homomorphic characterizations of recursively enumerable languages with very small language classes ⋮ Sublogarithmic ambiguity ⋮ A note on bounded-reversal multipushdown machines ⋮ Counter machines and verification problems. ⋮ A characterization of reversal-bounded multipushdown machine languages ⋮ Two-way counter machines and finite-state transducers† ⋮ On Computational Power of Partially Blind Automata ⋮ Unresolved systems of language equations: expressive power and decision problems

Cites Work