The complexity of decision problems for finite-turn multicounter machines
- 1 April 1981
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 22 (2) , 220-229
- https://doi.org/10.1016/0022-0000(81)90028-3
Abstract
No abstract availableKeywords
Funding Information
- National Science Foundation (MCS78-01736, MCS79-09967)
This publication has 11 references indexed in Scilit:
- An NP-Complete Number-Theoretic ProblemJournal of the ACM, 1979
- Reversal-Bounded Multicounter Machines and Their Decision ProblemsJournal of the ACM, 1978
- Remarks on the complexity of nondeterministic counter languagesTheoretical Computer Science, 1976
- Hierarchies of complete problemsActa Informatica, 1976
- Space-bounded reducibility among combinatorial problemsJournal of Computer and System Sciences, 1975
- Reversal-bounded multipushdown machinesJournal of Computer and System Sciences, 1974
- The equivalence problem for deterministic finite-turn pushdown automataInformation and Control, 1974
- An Infinite Hierarchy of Context-Free LanguagesJournal of the ACM, 1969
- Counter machines and counter languagesTheory of Computing Systems, 1968
- Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing MachinesAnnals of Mathematics, 1961