CRN Elimination and Substitution Bases for Complexity Classes

Article type: Research Article

Authors: Mazzanti, Stefano

Affiliations: Facoltà di Design e Arti, Università Iuav di Venezia, Fondamenta delle Terese 2206, 30123 Venezia, Italy, mazzanti@iuav.it

Note: [] Address for correspondence: Facoltà di Design e Arti, Università Iuav di Venezia, Fondamenta delle Terese 2206, 30123 Venezia, Italy

Abstract: Function classes closed with respect to substitution and concatenation recursion on notation are characterized as the substitution closure of finite function sets. Consequently, the sets of TC0, NC1 and L computable functions are characterized as the substitution closure of a finite function set.

Keywords: concatenation recursion on notation, substitution basis

DOI: 10.3233/FI-2012-748

Journal: Fundamenta Informaticae, vol. 120, no. 1, pp. 29-58, 2012