Please use this identifier to cite or link to this item:
|Title:||The dot-depth and the polynomial hierarchies correspond on the delta levels|
|Citation:||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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 17, 2018
WEB OF SCIENCETM
checked on May 9, 2018
checked on May 12, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.