Premium
New substitution bases for complexity classes
Author(s) -
Mazzanti Stefano
Publication year - 2020
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201800055
Subject(s) - closure (psychology) , substitution (logic) , concatenation (mathematics) , mathematics , simple (philosophy) , recursion (computer science) , set (abstract data type) , set function , function (biology) , notation , discrete mathematics , algebra over a field , combinatorics , pure mathematics , algorithm , arithmetic , computer science , programming language , philosophy , epistemology , evolutionary biology , economics , market economy , biology
The setAC 0 ( F ) , the AC 0 closure of F , is the closure with respect to substitution and concatenation recursion on notation of a set of basic functions comprehending the set F . By improving earlier work, we show thatAC 0 ( F )is the substitution closure of a simple function set and characterize well‐known function complexity classes as the substitution closure of finite sets of simple functions.