Reversal Complexity Classes for Alternating Turing Machines
Mirosław Kutyłowski, Maciej Liśkiewicz, Krzysztof Loryś · SIAM Journal on Computing · 1990
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.