On the complexity of decision problems for some classes of machines and applications
Date
2023-10
Authors
Ibarra, Oscar H.
McQuillan, Ian
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
ORCID
Type
Article
Degree Level
Abstract
We study the computational complexity of important decision problems — including general membership, fixed-machine membership, emptiness, disjointness, equivalence, containment, universe, and finiteness problems — for various restrictions and combinations of two-way nondeterministic reversal-bounded multicounter machines (2 NCM) and two-way pushdown automata. We show that the general membership problem (respectively fixed membership problem) for 2 NCM is NP-complete (respectively in P).
We then give applications to some problems in coding theory. We examine generalizations of various types of codes with marginal errors. For example, a language L is k-infix-free if there is no non-empty string y in L that is an infix of more than k strings in L - {y}. Our general results imply the complexity of determining whether a given machine accepts a k-infix-free language, for one- and two-way deterministic and nondeterministic finite automata (answering an open question from the literature).
Description
This is the accepted manuscript of the original article "On the complexity of decision problems for some classes of machines and applications" (https://doi.org/10.1016/j.ic.2023.105080) published in the journal "Information and Computation" published by Elsevier.
Keywords
Counter machines, Reversal-bounded counters, Decidable, Undecidable, Computational complexity, Coding theory
Citation
Ibarra, O. H., & McQuillan, I. (2023). On the complexity of decision problems for some classes of machines and applications. Information and Computation, 294, 105080. https://doi.org/10.1016/j.ic.2023.105080
Degree
Department
Program
Advisor
Committee
Part Of
item.page.relation.ispartofseries
DOI
https://doi.org/10.1016/j.ic.2023.105080