Premium
Iteration on notation and unary functions
Author(s) -
Mazzanti Stefano
Publication year - 2013
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.201200055
Subject(s) - concatenation (mathematics) , notation , unary operation , mathematics , recursion (computer science) , mutual recursion , function (biology) , discrete mathematics , algebra over a field , algorithm , combinatorics , arithmetic , pure mathematics , evolutionary biology , biology
In the first half of the 1990s, Clote and Takeuti characterized several function complexity classes by means of the concatenation recursion on notation operators. In this paper, we borrow from computability theory well‐known techniques based on pairing functions to show thatAC 0 , TC 0 , NC 1 , and NC functions can be characterized by means of concatenation iteration on notation. Indeed, a function class satisfying simple constraints and defined by using concatenation recursion on notation is inductively characterized by means of concatenation iteration on notation. Furthermore,AC 0 , TC 0 , NC 1 , and NC unary functions are inductively characterized using addition, composition, and concatenation iteration on notation.