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

DSpace Repositorium (Manakin basiert)

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
Zitierfähiger Link (URI): http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-12234
http://hdl.handle.net/10900/48599
Dokumentart: Verschiedenartige Texte
Erscheinungsdatum: 2004
Originalveröffentlichung: WSI ; 2004 ; 3
Sprache: Englisch
Fakultät: 7 Mathematisch-Naturwissenschaftliche Fakultät
Fachbereich: Sonstige - Informations- und Kognitionswissenschaften
DDC-Klassifikation: 004 - Informatik
Schlagworte: Komplexitätsklasse , Dot-Depth-Hierarchie , Straubing-Thérien-Hierarchie , Komplexitätsklasse NP
Freie Schlagwörter: Polynomialzeit-Hierarchie
Lizenz: http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=de http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=en
Zur Langanzeige

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.

Das Dokument erscheint in: