An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines
type: Item
instance of: scholarly article
title: An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines
zbMATH Open document ID: 0629.68054
DOI: 10.1016/0022-0000(87)90005-5
author: Rodney R. Howell
author: Louis E. Rosier
published in: Journal of Computer and System Sciences
publication date: 1987-01-01T00:00:00Z
review text: In this paper, we present an efficient nondeterministic algorithm to decide nonemptiness for reversal-bounded multicounter machines. This algorithm executes in time polynomial in the size of the input and the number of reversals the counters are allowed. Previously the best known upper bound required space logarithmic in the size of the input and linear in the number of reversals. We argue that our algorithm is within some polynomial function of the optimal nondeterministic run time for many classes of these machines. Furthermore, we show that in most cases, the complexity of the nonemptiness problem does not change significantly when the reversal bound is dropped for one of the counters. In addition, we explore the changes in the complexity of the nonemptiness problem for these classes as different parameters are fixed or are given in either unary or binary. Our results yield as corollaries the answers to several unanswered questions regarding the disjointness, equivalence, and containment problems for reversal-bounded multicounter machines. Finally, we use our results to solve several problems regarding deadlock detection and unboundedness detection for systems of communicating finite state machines.
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4024795
zbMATH Keywords: efficient nondeterministic algorithm
zbMATH Keywords: nonemptiness
zbMATH Keywords: reversal-bounded multicounter machines
zbMATH Keywords: communicating finite state machines
MaRDI profile type: Publication
full work available at URL: 0022-0000(87)90005-5
OpenAlex ID: W2072212606
cites work: Reversal-bounded multipushdown machines
cites work: Bounds on Positive Integral Solutions of Linear Diophantine Equations
cites work: On Communicating Finite-State Machines
cites work: The complexity of theorem-proving procedures
cites work: Turing machines with restricted memory access
cites work: Hierarchies of complete problems
cites work: Q4198056
cites work: Deterministic context free languages
cites work: An Infinite Hierarchy of Context-Free Languages
cites work: An NP-Complete Number-Theoretic Problem
cites work: The complexity of decision problems for finite-turn multicounter machines
cites work: Q3862379
cites work: Reversal-Bounded Multicounter Machines and Their Decision Problems
cites work: On the decidability of equivalence for deterministic pushdown transducers
cites work: Space-bounded reducibility among combinatorial problems
cites work: Q4142699
cites work: Recursive unsolvability of Post's problem of ''Tag'' und other topics in theory of Turing machines
cites work: Classes of Recursively Enumerable Sets and Their Decision Problems
description: scientific article; zbMATH DE number 4024795