scientific article; zbMATH DE number 3974295
[For the entire collection see Zbl 0596.00021.] 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.
- An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines
- Counter machines and verification problems.
- Counter machines: Decidable properties and applications to verification problems
- New Decidability Results Concerning Two-Way Counter Machines
- New decidability results concerning two-way counter machines and applications
- An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines
- Reversal-bounded multicounter ?-machines
- On the emptiness problem for two-way NFA with one reversal-bounded counter
- Reachability analysis for some models of infinite-state transition systems
- On reachability and safety in infinite-state systems
- Unboundedness problems for machines with reversal-bounded counters
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3740236)