A decidable characterization of the classes between lintime and exptime

作     者：Caporaso, S 

作者机构：Univ Bari Dipartimento Informat I-70125 Bari Italy 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2006年第97卷第1期

页      面：36-40页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：computational complexity implicit computational complexity theory of computation 

摘      要：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-alpha (alpha = 0. (c) 2005 Elsevier B.V. All rights reserved.