The set 0(), the 0 closure of F , is the closure with respect to substitution and concatenation recursion on notation of a set of basic functions comprehending the set F . By improving earlier work, we show that 0() is the substitution closure of a simple function set and characterize well‐known function complexity classes as the substitution closure of finite sets of simple functions.
New substitution bases for complexity classes
Stefano Mazzanti
2020-01-01
Abstract
The set 0(), the 0 closure of F , is the closure with respect to substitution and concatenation recursion on notation of a set of basic functions comprehending the set F . By improving earlier work, we show that 0() is the substitution closure of a simple function set and characterize well‐known function complexity classes as the substitution closure of finite sets of simple functions.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
improved-bases-11.pdf
accesso aperto
Descrizione: Articolo principale
Tipologia:
Documento in Pre-print
Licenza:
Creative commons
Dimensione
357.81 kB
Formato
Adobe PDF
|
357.81 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
