Skip to Main content Skip to Navigation
Conference papers

Intensional properties of polygraphs

Guillaume Bonfante 1 Yves Guiraud 2
1 CARTE - Theoretical adverse computations, and safety
LORIA - FM - Department of Formal Methods , Inria Nancy - Grand Est
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.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Yves Guiraud Connect in order to contact the contributor
Submitted on : Friday, November 9, 2007 - 4:00:48 PM
Last modification on : Saturday, October 16, 2021 - 11:26:05 AM
Long-term archiving on: : Friday, November 25, 2016 - 5:47:56 PM


Files produced by the author(s)




Guillaume Bonfante, Yves Guiraud. Intensional properties of polygraphs. 4th International Workshop on Computing with Terms and Graphs - TERMGRAPH 2007, Mar 2007, Braga, Portugal. ⟨10.1016/j.entcs.2008.03.034⟩. ⟨inria-00129391v3⟩



Record views


Files downloads