Please use this identifier to cite or link to this item: https://doi.org/10.1142/S0129054105003200
Title: The dot-depth and the polynomial hierarchies correspond on the delta levels
Authors: Borchert, B.
Lange, K.-J.
Stephan, F. 
Tesson, P.
Thérien, D.
Issue Date: 2005
Source: Borchert, B., Lange, K.-J., Stephan, F., Tesson, P., Thérien, D. (2005). The dot-depth and the polynomial hierarchies correspond on the delta levels. International Journal of Foundations of Computer Science 16 (4) : 625-644. ScholarBank@NUS Repository. https://doi.org/10.1142/S0129054105003200
Abstract: It is well-known that the ∑ k- and Π k-levels of the dot-depth hierarchy and the polynomial hierarchy correspond via leaf languages. We extend this correspondence to the Δ k-levels of these hierarchies: Leaf P(Δ k L) = Δ k P. The same methods are used to give evidence against an earlier conjecture of Straubing and Thérien about a leaf-language upper bound for BPP. © World Scientific Publishing Company.
Source Title: International Journal of Foundations of Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/40813
ISSN: 01290541
DOI: 10.1142/S0129054105003200
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

3
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

3
checked on Nov 19, 2017

Page view(s)

51
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.