On the complexity of decision problems for some classes of machines and applications

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 (2NCM) and twoway pushdown automata. We show that the general membership problem (respectively fixed membership problem) for 2NCM 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). (c) 2023 Elsevier Inc. All rights reserved.