2006/09/23 by Salvatore Caporaso, Caporaso, Salvatore
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.CC #cs.LO
paper · pdf · doi:10.48550/arxiv.cs/0609130
11 pages
arxiv created 2006/09/23 · arxiv updated 2009/12/01
A decidable transfinite hierarchy is defined by assigning ordinals to the programs of an imperative language. It singles out: the classes TIMEF(nc) and TIMEF(nc); the finite Grzegorczyk classes at and above the elementary level, and the Σk-IND fragments of PA. Limited operators, diagonalization, and majorization functions are not used.