Bounded alternation

Show full item record

Title: Bounded alternation
Author: Radziszowski, Stanislaw
Abstract: We consider alternating Turing machines with the bound the number of alternations given by some function. By on restricting the class of machines to those operating in polynomial time we obtain the hierarchy of classes between n≥o ∑pn (the sum of polynomial-time hierarchy of Stockmeyer) and PSPACE. We exhibit some problems to be complete in a special sense in the class of problems solvable by alternating Turing machines performing at most f(n) alternations. Also conditional inequalities between classes are derived. The second part of tpe paper relates these results to the measure STA introduced by Berman [2]. Several properties of that measure are presented. *Please refer to full-text for proper formulas
Record URI: http://hdl.handle.net/1850/9816
Date: 1980

Files in this item

Files Size Format View
SRadziszowskiArticle10-24-1980.pdf 10.59Mb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse