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 that AC0,TC0, NC1, 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, AC0,TC0, NC1, and NC unary functions are inductively characterized using addition, composition, and concatenation iteration on notation.

Iteration on notation and unary functions

MAZZANTI, STEFANO
2013

Abstract

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 that AC0,TC0, NC1, 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, AC0,TC0, NC1, and NC unary functions are inductively characterized using addition, composition, and concatenation iteration on notation.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11578/140888
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact