The set AC0(F), the AC0 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 AC0(F) 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
Mazzanti, Stefano
2020-01-01
Abstract
The set AC0(F), the AC0 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 AC0(F) 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 | |
|---|---|---|---|
|
NEW-SUBSTITUTION-BASES-Published.pdf
non disponibili
Descrizione: Articolo principale
Tipologia:
Versione Editoriale
Licenza:
Accesso ristretto
Dimensione
255.39 kB
Formato
Adobe PDF
|
255.39 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
