Intensional properties of polygraphs

Guillaume Bonfante 1 Yves Guiraud 2
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
2 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present polygraphic programs, a subclass of Albert Burroni's polygraphs, as a computational model, showing how these objects can be seen as first-order functional programs. We prove that the model is Turing complete. We use polygraphic interpretations, a termination proof method introduced by the second author, to characterize polygraphic programs that compute in polynomial time. We conclude with a characterization of polynomial time functions.
Type de document :
Communication dans un congrès
4th International Workshop on Computing with Terms and Graphs - TERMGRAPH 2007, Mar 2007, Braga, Portugal. 203(1):65-77, 2008, Electronic Notes in Theoretical Computer Science. 〈10.1016/j.entcs.2008.03.034〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00129391
Contributeur : Yves Guiraud <>
Soumis le : vendredi 9 novembre 2007 - 16:00:48
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 17:47:56

Fichier

termgraph.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Guillaume Bonfante, Yves Guiraud. Intensional properties of polygraphs. 4th International Workshop on Computing with Terms and Graphs - TERMGRAPH 2007, Mar 2007, Braga, Portugal. 203(1):65-77, 2008, Electronic Notes in Theoretical Computer Science. 〈10.1016/j.entcs.2008.03.034〉. 〈inria-00129391v3〉

Partager

Métriques

Consultations de la notice

283

Téléchargements de fichiers

128