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

DSpace Repository

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

Borchert, Bernd; Lange, Klaus-Joern; Stephan, Frank; Tesson, Pascal; Therien, Denis
Dateien:
Thumbnail
193. KB
PDF
URI: http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-12234
http://hdl.handle.net/10900/48599
Dokumentart: Report (Bericht)
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
License: xmlui.dri2xhtml.METS-1.0.item-dc-rights_value_ubt-nopod
Show full item record

Abstract:

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)