Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657757 | Theoretical Computer Science | 2005 | 25 Pages |
Abstract
Hierarchies considered in computability theory and in complexity theory are related to some reducibilities in the sense that levels of the hierarchies are downward closed and have complete sets. In this paper we propose a reducibility having similar relationship to the Brzozowski's dot-depth hierarchy and some its refinements. We prove some basic facts on the corresponding degree structure and discuss relationships of the reducibility to complexity theory (via the leaf-language approach).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Victor L. Selivanov, Klaus W. Wagner,