Reversal Complexity Classes for Alternating Turing Machines
Lists
Only you see this
Abstract
Alternating Turing machines (ATMs) with bounded number of reversals are considered. It is proved that the machines making fewer than $\log ^{*} n$ reversals can recognize only regular languages. On the other hand, the class of languages that can be recognized by ATMs using $\log ^{*} n$ reversals is very wide. The authors prove that above this limit even a slight increase of the number of reversals leads to a considerably larger class of languages. It is also proved that every $T(n)$-time bounded ATM may be replaced by an equivalent machine working in the same time and making no more than $\log ^{*} (T(n))$ reversals.
BibTeX
@article{kutylowski1990reversal,
author = {Miroslaw Kutylowski and Maciej Liskiewicz and Krzysztof Lorys},
title = {{Reversal Complexity Classes for Alternating Turing Machines}},
journal = {SIAM Journal on Computing},
year = {1990},
doi = {10.1137/0219014},
}Loading related content...