On reversal complexity for alternating Turing machines
Maciej Liśkiewicz, Krzysztof Loryś · 1989
The reversal complexity of alternating Turing machines (ATM) is investigated. The strict lower bounds on reversals for recognizing nonregular languages by Sigma /sub k/ machines are settled. Some results relating reversal and space complexities are obtained.>