The dot-depth and the polynomial hierarchy correspond on the delta levels

DSpace Repository


Dokumentart: Report
Date: 2004
Source: WSI ; 2004 ; 3
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Sonstige - Informations- und Kognitionswissenschaften
DDC Classifikation: 004 - Data processing and computer science
Keywords: Komplexitätsklasse , Dot-Depth-Hierarchie , Straubing-Thérien-Hierarchie , Komplexitätsklasse NP
Other Keywords: Polynomialzeit-Hierarchie
Show full item record


It is well-known that the Sigma_k- and Pi_k-levels of the dot-depth hierarchy and the polynomial hierarchy correspond via leaf languages. In this paper this correspondence will be extended to the Delta_k-levels of these hierarchies: Leaf^P(Delta_k^L) = Delta_k^p.

This item appears in the following Collection(s)