Please use this identifier to cite or link to this item:
|Title:||The dot-depth and the polynomial hierarchy correspond on the delta levels||Authors:||Borchert, B.
|Issue Date:||2004||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)||URI:||http://scholarbank.nus.edu.sg/handle/10635/39650||ISSN:||03029743|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jun 30, 2020
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.