New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines
Date
2023-06
Authors
Ibarra, Oscar H.
McQuillan, Ian
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
ORCID
Type
Article
Degree Level
Abstract
Machine models with multiple types of stores are studied. Deterministic two-way pushdown automata augmented by some number of checking stacks are known to accept exactly the class of elementary languages, which is very general but still has a decidable membership problem. First, we define such a machine to be synchronous if, when a checking stack starts to read from its stack, all other checking stacks can no longer write. For such a synchronous machine, the multiple checking stacks are equivalent to machines with 2 synchronous checking stacks which, in turn, are equivalent to exponential time-bounded deterministic Turing machines. Next, we also show that for any (reasonably defined) one-way deterministic machine model M with a decidable membership problem, the two-way deterministic multi-head variant of M augmented by any number of checking stacks also has a decidable membership problem. We also examine a model, two-way deterministic pushdown automata augmented with some number of non-erasing stacks, where the machine starts reading from the stacks at most a linear number of times. We show that this model accepts non-elementary languages but still has a decidable membership problem, resolving an open problem from the literature.
Description
This is the accepted manuscript of the original article "New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines" (https://doi.org/10.1016/j.ic.2023.105027) published in the journal "Information and Computation" published by Elsevier.
Keywords
Stack automata, Checking stack automata, Turing machines, Complexity classes, Elementary languages
Citation
Ibarra, O. H., & McQuillan, I. (2023). New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines. Information and Computation, 292, 105027. https://doi.org/10.1016/j.ic.2023.105027
Degree
Department
Program
Advisor
Committee
Part Of
item.page.relation.ispartofseries
DOI
https://doi.org/10.1016/j.ic.2023.105027