Article ID Journal Published Year Pages File Type
9657757 Theoretical Computer Science 2005 25 Pages PDF
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).
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,