Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
type: Item
instance of: scholarly article
title: Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
zbMATH Open document ID: 0631.68051
DOI: 10.1016/0890-5401(87)90055-1
author: Hiroaki Yamamoto
author: Shoichi Noguchi
published in: Information and Computation
publication date: 1987-01-01T00:00:00Z
review text: Alternating Turing machines (ATMs) are a generalization of non- deterministic Turing machines (NTMs). It is said that an ATM runs in reversal \(R(n)\) (resp. leaf \(B(n))\) if for every accepted input of length n there is a computation tree such that for each path from the root to a leaf the number of times a head changes the direction is at most \(R(n)\) (resp. the number of leaves is at most \(B(n)\)). In the paper, the power of reversal-bounded ATMs is considered and the results are as follows: 1. Every recursively enumerable set can be accepted by a 1-type 1-counter ATM with runs in constant reversals but not by a 1-type 1-counter NTM which runs in constant reversals. 2. For \(B(n)\) and \(R(n)\) satisfying \(B(n)\leq 2^{O(R(n))}\) and \(B(n)R(n)\geq n\), a class of languages accepted by 1-type ATMs which run in \(O(R(n))\) reversal and \(O(B(n))\) leaf is equivalent to a class of languages accepted by NTMs which run in \(O(B(n)R(n))\) space.
reviewed by: M.Kratko
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D10
zbMATH DE Number: 4026837
zbMATH Keywords: reversal-bounded machine
zbMATH Keywords: Alternating Turing machines
zbMATH Keywords: non-deterministic Turing machines
zbMATH Keywords: recursively enumerable set
MaRDI profile type: Publication
full work available at URL: 0890-5401(87)90055-1
OpenAlex ID: W2087846761
cites work: Reversal-bounded multipushdown machines
cites work: Alternation
cites work: The reduction of tape reversals for off-line one-tape Turing machines
cites work: Visits, crosses, and reversals for nondeterministic off-line machines
cites work: Tape-reversal bounded Turing machine computations
cites work: Relations Between Time and Tape Complexities
cites work: Alternating multicounter machines with constant number of reversals
cites work: Q3725549
cites work: Note on tape reversal complexity of languages
cites work: Tree-size bounded alternation
cites work: Techniques for separating space complexity classes
description: scientific article; zbMATH DE number 4026837