An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines

DOI10.1016/0022-0000(87)90005-5zbMath0629.68054OpenAlexW2072212606MaRDI QIDQ1094140

Rodney R. Howell, Louis E. Rosier

Publication date: 1987

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(87)90005-5

zbMATH Keywords

nonemptinesscommunicating finite state machinesefficient nondeterministic algorithmreversal-bounded multicounter machines

Mathematics Subject Classification ID

Related Items (3)

The Complexity of Reversal-Bounded Model-Checking ⋮ On selective unboundedness of VASS ⋮ Communicating processes, scheduling, and the complexity of nontermination

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The complexity of decision problems for finite-turn multicounter machines
• On the decidability of equivalence for deterministic pushdown transducers
• Hierarchies of complete problems
• Reversal-bounded multipushdown machines
• Space-bounded reducibility among combinatorial problems
• On Communicating Finite-State Machines
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• An NP-Complete Number-Theoretic Problem
• Deterministic context free languages
• Turing machines with restricted memory access
• An Infinite Hierarchy of Context-Free Languages
• The complexity of theorem-proving procedures
• Classes of Recursively Enumerable Sets and Their Decision Problems

This page was built for publication: An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines