ON REVERSAL COMPLEXITY FOR ALTERNATING TURING MACHINES (Extended abstract)
Maciej Liśkiewicz, Krzysztof Loryś · Foundations of Computer Science · 1989
The reversal complexity of alternating Turing machines (ATM) is investigated.It is shown that CkREV(R(n))$Z Ck+lREV(R(n)) for every k€N and every reversal constructible function Rfn) 1 ( The question whether the similar hierarchy holds for time complexity is still an open problem; for space complexity this hierarchy collapses.) The strict lower bounds on reversals for recognizing nonregular languages by Ck machines are settled. Some results relating reversal and space complexities are obtained ( e.g. it is shown that PSPACE = Z2REV(los n)).