Please use this identifier to cite or link to this item:
|Title:||The dot-depth and the polynomial hierarchy correspond on the delta levels|
|Citation:||Borchert, B.,Lange, K.-J.,Stephan, F.,Tesson, P.,Thérien, D. (2004). The dot-depth and the polynomial hierarchy correspond on the delta levels. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3340 : 89-101. ScholarBank@NUS Repository.|
|Abstract:||The leaf-language mechanism associates a complexity class to a class of regular languages. It is well-known that the Σ κ- and Π κ-levels of the dot-depth hierarchy and the polynomial hierarchy correspond in this formalism. We extend this correspondence to the Δ κ-levels of these hierarchies: Leaf P(Δ κ L) = Δ κ Ρ. These results are obtained in part by relating operators on varieties of languages to operators on the corresponding complexity classes. © Springer-Verlag Berlin Heidelberg 2004.|
|Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Nov 3, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.