Bases for AC⁰ and Other Complexity Classes

Article type: Research Article

Authors: Mazzanti, Stefano

Affiliations: Dipartimento di Culture del Progetto, Università Iuav di Venezia, Fondamenta delle Terese 2206, 30123 Venezia, Italy. mazzanti@iuav.it

Note: [] Address for correspondence: Dipartimento di Culture del Progetto, Università Iuav di Venezia, Fondamenta delle Terese 2206, 30123 Venezia, Italy

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.

Keywords: concatenation recursion on notation, substitution basis

DOI: 10.3233/FI-2015-1165

Journal: Fundamenta Informaticae, vol. 136, no. 4, pp. 433-460, 2015