Any partial recursive function can be computed at compile time, using C++ templates to define primitive recursion, composition, and minimalization. In this paper, we define a restricted language based on C++ templates, and we prove that it characterizes the set of polynomial-time computable functions, that is the set of functions computed by a Turing machine with time bounded by a polynomial.
Complexity certification of C++ template metaprogramming (extended version)
PANI, Giovanni;COVINO, Emanuele
2009-01-01
Abstract
Any partial recursive function can be computed at compile time, using C++ templates to define primitive recursion, composition, and minimalization. In this paper, we define a restricted language based on C++ templates, and we prove that it characterizes the set of polynomial-time computable functions, that is the set of functions computed by a Turing machine with time bounded by a polynomial.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.
