The complexity of decision problems for finite-turn multicounter machines
From MaRDI portal
Publication:1151753
DOI10.1016/0022-0000(81)90028-3zbMath0458.68011OpenAlexW1979876920MaRDI QIDQ1151753
Oscar H. Ibarra, Eitan M. Gurari
Publication date: 1981
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(81)90028-3
Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Related Items
Some decision problems concerning semilinearity and commutation. ⋮ A note on finite-valued and finitely ambiguous transducers ⋮ Lossiness of communication channels modeled by transducers1 ⋮ On two-way FA with monotonic counters and quadratic Diophantine equations ⋮ Finite-valued distance automata ⋮ The Complexity of Reversal-Bounded Model-Checking ⋮ An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines ⋮ Quantifying communication in synchronized languages ⋮ Pushdown automata with reversal-bounded counters ⋮ Quantifying Communication in Synchronized Languages ⋮ On the complexity of decision problems for counter machines with applications to coding theory ⋮ Families of languages defined by ciliate bio-operations ⋮ Deletion operations on deterministic families of automata ⋮ Similarity in languages and programs ⋮ On the decidability of the valuedness problem for two-way finite transducers ⋮ On store languages and applications ⋮ On two-way weak counter machines ⋮ On the complexity of decision problems for some classes of machines and applications ⋮ On counting functions and slenderness of languages ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ Insertion operations on deterministic reversal-bounded counter machines ⋮ Verification in loosely synchronous queue-connected discrete timed automata. ⋮ Pushdown timed automata: A binary reachability characterization and safety verification. ⋮ On the containment and equivalence problems for two-way transducers ⋮ Input-Position-Restricted Models of Language Acceptors ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ Unnamed Item ⋮ On the complexity and decidability of some problems involving shuffle ⋮ Unnamed Item ⋮ Deciding freeness for program schemes with a single unary function ⋮ ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS ⋮ On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals ⋮ 2DST mappings of languages and related problems ⋮ On the Decidability of the Equivalence for k-Valued Transducers ⋮ Static analysis of XML security views and query rewriting ⋮ Reachability analysis of reversal-bounded automata on series-parallel graphs ⋮ Nondeterministic Streaming String Transducers ⋮ Accepting runs in a two-way finite automaton ⋮ INDUCTIVE COMPOSITION OF NUMBERS WITH MAXIMUM, MINIMUM, AND ADDITION: A New Theory for Program Execution-Time Analysis ⋮ VERIFICATION IN QUEUE-CONNECTED MULTICOUNTER MACHINES ⋮ THE EXISTENCE OF ω-CHAINS FOR TRANSITIVE MIXED LINEAR RELATIONS AND ITS APPLICATIONS ⋮ State grammars with stores ⋮ CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES ⋮ On two-way nondeterministic finite automata with one reversal-bounded counter ⋮ On the Ambiguity and Finite-Valuedness Problems in Acceptors and Transducers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Grammatical characterizations of NPDAs and VPDAs with counters ⋮ On store languages of language acceptors ⋮ A technique for proving decidability of containment and equivalence of linear constraint queries ⋮ Some classes of languages in \(NC^ 1\) ⋮ On decidability and closure properties of language classes with respect to bio-operations ⋮ SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS ⋮ ON REACHABILITY AND SAFETY IN INFINITE-STATE SYSTEMS ⋮ On families of full trios containing counter machine languages ⋮ A note on Parikh maps, abstract languages, and decision problems ⋮ Modelization of deterministic rational relations ⋮ Sequential grammars and automata with valences
Cites Work
- Unnamed Item
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- Hierarchies of complete problems
- Deterministic one-counter automata
- Reversal-bounded multipushdown machines
- Space-bounded reducibility among combinatorial problems
- Remarks on the complexity of nondeterministic counter languages
- A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors
- Bounds on Positive Integral Solutions of Linear Diophantine Equations
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- An NP-Complete Number-Theoretic Problem
- The equivalence problem for deterministic finite-turn pushdown automata
- Counter machines and counter languages
- An Infinite Hierarchy of Context-Free Languages
This page was built for publication: The complexity of decision problems for finite-turn multicounter machines
