Reversal Complexity Classes for Alternating Turing Machines

Miroslaw Kutylowski, Maciej Liskiewicz, Krzysztof LorysSIAM Journal on Computing 1990 · DOI · OpenReview

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...

Figure