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

چکیده انگلیسی
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
Journal: Information Processing Letters - Volume 97, Issue 1, 16 January 2006, Pages 36-40