ScholarLens Back to search
1989•Foundations of Computer ScienceRequires access

ON REVERSAL COMPLEXITY FOR ALTERNATING TURING MACHINES (Extended abstract)

Maciej Liśkiewicz, Krzysztof Loryś

Open publisher page 0 citations

Abstract

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

About this research paper

What this paper is about

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

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

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

Key concepts: Turing machine, Time hierarchy theorem, Complexity class, DTIME, PSPACE, Hierarchy, NSPACE, Computational complexity theory

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
ON REVERSAL COMPLEXITY FOR ALTERNATING TURING MACHINES (Extended abstract) — Research Paper | ScholarLens