Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428425 | Information Processing Letters | 2006 | 5 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics