کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428425 686653 2006 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A decidable characterization of the classes between lintime and exptime
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A decidable characterization of the classes between lintime and exptime
چکیده انگلیسی

A language is defined by closure under safe iteration and under a new form of safe diagonalization that, unlike other forms of diagonalization used in literature to define sub-recursive hierarchies, is constructive and decidable. By counting the nesting levels of these schemes, an ordinal is assigned to each program. This yields a hierarchy Tα (α<ωω) that singles-out the complexity classes DTIMEF(ncnd+e) for all c,d,e⩾0.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 97, Issue 1, 16 January 2006, Pages 36-40