کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9657757 690565 2005 25 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A reducibility for the dot-depth hierarchy
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A reducibility for the dot-depth hierarchy
چکیده انگلیسی
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).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 345, Issues 2–3, 22 November 2005, Pages 448-472
نویسندگان
, ,