A
Reducibility for the Dot-Depth Hierarchy
Victor L. Selivanov
A.P. Ershov Institute of Informatics Systems
Siberian Division of the Russian Academy of Sciences
vseliv@ngs.ru
and
Klaus W. Wagner
Institut für Informatik
Julius-Maximilians-Universität Würzburg
wagner@informatik.uni-wuerzburg.de
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).