We define a version of predicative recursion, a related programming language, and a hierarchy of classes of programs that represents a resource-free characterization of register machines computing their output within polynomial time O(n^k), for each finite k. Then, we introduce an operator of diagonalization, that allows us to extend the previous hierarchy and to capture the register machines with computing time bounded by an exponential limit O(n^n^k ). Finally, by means of a restriction on composition of programs, we characterize the register machines with a polynomial bound imposed over time and space complexity, simultaneously.
Predicative recursion, diagonalization, and slow-growing hierarchies of time-bounded programs
COVINO, Emanuele;PANI, Giovanni
2015-01-01
Abstract
We define a version of predicative recursion, a related programming language, and a hierarchy of classes of programs that represents a resource-free characterization of register machines computing their output within polynomial time O(n^k), for each finite k. Then, we introduce an operator of diagonalization, that allows us to extend the previous hierarchy and to capture the register machines with computing time bounded by an exponential limit O(n^n^k ). Finally, by means of a restriction on composition of programs, we characterize the register machines with a polynomial bound imposed over time and space complexity, simultaneously.File | Dimensione | Formato | |
---|---|---|---|
ijais 2015.pdf
accesso aperto
Descrizione: articolo principale
Tipologia:
Documento in Versione Editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
116.06 kB
Formato
Adobe PDF
|
116.06 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.