On Decision Problems for Parameterized Machines
Journal
Theoretical Computer Science
Journal Volume
411
Journal Issue
7-9
Pages
1192-1201
Date Issued
2010-01
Author(s)
Abstract
In this paper, we investigate various decision problems concerning parameterized versions of some classes of machines. Let C (s, m, t) be the class of nondeterministic multitape Turing machine (TM) acceptors with a two-way read-only input, at most s states, at most m read-write worktapes, and at most t symbols in the worktape alphabet, where s, m, t are fixed positive integers. There is no restriction on the cardinality of the input alphabet. We are able to show the emptiness, disjointness, and universe (also called universality) problems to be decidable for C (s, m, t). For the class consisting of machines in C (s, m, t) that always halt or whose minimal-time accepting computations can be bounded by some recursive function f (n) (where n is the input length), the containment and equivalence problems are decidable. These results hold for other machines, e.g., when the worktapes are pushdown stacks (where on every step, each pushdown can only pop the top of the stack or replace the top of the stack by at most two symbols) or when stacks are counters (where on every step, a counter can be incremented by 1, decremented by 1, or remain unchanged, and can be tested for zero). Our results are the best possible in the sense that not parameterizing one of s, m, t (or, in the case of counter machines, allowing the counters to increment by arbitrary integers that may change from machines to machines) makes the universe problem undecidable. We also give a simple characterization of the languages defined by C (s, m, t). Finally, we investigate the applicability of our techniques to machines with multiple input heads or multiple input tapes. © 2009 Elsevier B.V. All rights reserved.
SDGs
Type
journal article