Any partial recursive function can be computed at compile time, using C++ templates to define primitive recursion, composition, and minimalization. We define a sub-language based on C++ templates, which characterizes the set of functions computable by a Turing machine with time bounded by a polinomial. This language can be used as a form of complexity certification of programs.

Complexity certification of C++ templates

COVINO, Emanuele;PANI, Giovanni
2008-01-01

Abstract

Any partial recursive function can be computed at compile time, using C++ templates to define primitive recursion, composition, and minimalization. We define a sub-language based on C++ templates, which characterizes the set of functions computable by a Turing machine with time bounded by a polinomial. This language can be used as a form of complexity certification of programs.
2008
978-972-8924-63-8
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/11586/118051
 Attenzione

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

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