Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/39650
| Title: | The dot-depth and the polynomial hierarchy correspond on the delta levels | Authors: | Borchert, B. Lange, K.-J. Stephan, F. Tesson, P. Thérien, D. |
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.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.