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

DSpace Repository

Show simple item record

dc.contributor Wilhelm-Schickard-Institut de_CH
dc.contributor.author Borchert, Bernd de_DE
dc.contributor.author Lange, Klaus-Joern de_DE
dc.contributor.author Stephan, Frank de_DE
dc.contributor.author Tesson, Pascal de_DE
dc.contributor.author Therien, Denis de_DE
dc.date.accessioned 2004-05-17 de_DE
dc.date.accessioned 2014-03-18T10:12:40Z
dc.date.available 2004-05-17 de_DE
dc.date.available 2014-03-18T10:12:40Z
dc.date.issued 2004 de_DE
dc.identifier.other 111639034 de_DE
dc.identifier.uri http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-12234 de_DE
dc.identifier.uri http://hdl.handle.net/10900/48599
dc.description.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. en
dc.language.iso en de_DE
dc.publisher Universität Tübingen de_DE
dc.rights ubt-nopod de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=de de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=en en
dc.subject.classification Komplexitätsklasse , Dot-Depth-Hierarchie , Straubing-Thérien-Hierarchie , Komplexitätsklasse NP de_DE
dc.subject.ddc 004 de_DE
dc.subject.other Polynomialzeit-Hierarchie de_DE
dc.title The dot-depth and the polynomial hierarchy correspond on the delta levels en
dc.type Report (Bericht) de_DE
dc.date.updated 2012-10-11 de_DE
utue.publikation.fachbereich Sonstige - Informations- und Kognitionswissenschaften de_DE
utue.publikation.fakultaet 7 Mathematisch-Naturwissenschaftliche Fakultät de_DE
dcterms.DCMIType Text de_DE
utue.publikation.typ report de_DE
utue.opus.id 1223 de_DE
utue.opus.portal wsi de_DE
utue.opus.portalzaehlung 2004.03000 de_DE
utue.publikation.source WSI ; 2004 ; 3 de_DE
utue.publikation.reihenname WSI-Reports - Schriftenreihe des Wilhelm-Schickard-Instituts für Informatik de_DE
utue.publikation.zsausgabe 2004, 3
utue.publikation.erstkatid 2919855-0

Dateien:

This item appears in the following Collection(s)

Show simple item record