Bases for \(\mathrm{AC}^{0}\) and other complexity classes (Q2805414)

A finite function set \(F\) is a substitution basis for a function class \(G\) if \(G\) can be defined using only the functions in \(F\), the projection functions and the substitution operator. In this case \(G\) is called the substitution closure of \(F\). 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. Previously [Fundam. Inform. 120, No. 1, 29--58 (2012; Zbl 1260.03076)], the author showed that a function class closed with respect to substitution and concatenation recursion on notation admits a substitution basis, provided it contains integer division. In the paper under review, the author improves the techniques and results of this paper. For instance, the existence of a basis for a function class is stated without assuming that the division operation is in the class.