Intensional properties of polygraphs
Résumé
We present Albert Burroni's polygraphs as a computational model, showing how these objects can be seen as functional programs. First, we prove that the model is Turing complete. Then, we use a notion of termination proof introduced by the second author to characterize polygraphs that compute in polynomial time and, going further, polynomial time functions.
Origine : Fichiers produits par l'(les) auteur(s)