Article ID Journal Published Year Pages File Type
428425 Information Processing Letters 2006 5 Pages PDF
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