zbMATH — the first resource for mathematics

An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines. (English) Zbl 0629.68054
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.

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Baker, B.; Book, R., Reversal-bounded multipushdown machines, J. comput. system sci., 8, 315-322, (1974) · Zbl 0309.68043
[2] Borosh, I.; Treybig, L., Bounds on positive integral solutions of linear Diophantine equations, (), 299-304 · Zbl 0291.10014
[3] Brand, D.; Zafiropulo, P., On communicating finite-state machines, J. assoc. comput. Mach., 30, No. 2, 323-342, (1983) · Zbl 0512.68039
[4] Cook, S., The complexity of theorem-proving procedures, (), 151-158
[5] Fischer, P., Turing machines with restricted memory access, Inform. and control, 9, No. 4, 364-379, (1966) · Zbl 0145.24205
[6] Galil, Z., Hierarchies of complete problems, Acta inform., 6, 77-88, (1976) · Zbl 0304.68044
[7] Garey, M.; Johnson, D., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[8] Ginsburg, S.; Greibach, S., Deterministic context-free languages, Inform. and control, 9, 620-648, (1966) · Zbl 0145.00802
[9] Gouda, M.; Gurari, E.; Lai, T.; Rosier, L., On deadlock detection in systems of communicating finite state machines, (), Computers and artificial intelligence, (Apr. 1985), to appear
[10] Griebach, S., An infinite hierarchy of context-free languages, J. assoc. comput. Mach., 16, 91-106, (1969) · Zbl 0182.02002
[11] Gurari, E., Transducers with decidable equivalence problem, (), Revised 1982
[12] Gurari, E.; Ibarra, O., An NP-complete number-theoretic problem, J. assoc. comput. Mach., 26, 567-581, (1979) · Zbl 0407.68053
[13] Gurari, E.; Ibarra, O., The complexity of decision problems for finite-turn multicounter machines, J. comput. system sci., 22, No. 2, 220-229, (1981) · Zbl 0458.68011
[14] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, Mass · Zbl 0426.68001
[15] Ibarra, O., Reversal-bounded multicounter machines and their decision problems, J. assoc. comput. Mach., 25, 116-133, (1978) · Zbl 0365.68059
[16] Ibarra, O.; Rosier, L., On the decidability of equivalence for deterministic pushdown transducers, Inform. process. lett., 13, No. 3, 89-93, (1981) · Zbl 0473.68077
[17] Jones, N., Space-bounded reducibility among combinatorial problems, J. comput. system sci., 11, 68-85, (1975) · Zbl 0317.02039
[18] Karp, R., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[19] Minsky, M., Recursive unsolvability of Post’s problem of “tag” and other topics in the theory of Turing machines, Ann. of math., 74, No. 3, 437-455, (1961) · Zbl 0105.00802
[20] Rice, H., Classes of recursively enumerable sets and their decision problems, Trans. amer. math. soc., 89, 25-59, (1953) · Zbl 0053.00301
[21] Rosier, L.; Gouda, M., Deciding progress for a class of communicating finite state machines, (), 663-667
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.