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.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.
