Function complexity classes are defined as the substitution closure of finite function sets by improving a method of elimination of concatenation recursion from function algebras. Consequently, the set of AC0 functions and other canonical complexity classes are defined as the substitution closure of a finite function set.

Bases for AC0 and Other Complexity Classes

MAZZANTI, STEFANO
2015-01-01

Abstract

Function complexity classes are defined as the substitution closure of finite function sets by improving a method of elimination of concatenation recursion from function algebras. Consequently, the set of AC0 functions and other canonical complexity classes are defined as the substitution closure of a finite function set.
File in questo prodotto:
File Dimensione Formato  
Bases for AC0 and other Complexity Classes.pdf

non disponibili

Tipologia: Documento in Pre-print
Licenza: Accesso ristretto
Dimensione 411.69 kB
Formato Adobe PDF
411.69 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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11578/243897
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact