Bases for AC 0 and Other Complexity Classes
Stefano Mazzanti · Fundamenta Informaticae · 2015
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 AC 0 functions and other canonical complexity classes are defined as the substitution closure of a finite function set.