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

https://hal.inria.fr/inria-00129391
Contributor : Yves Guiraud <>
Submitted on : Friday, November 9, 2007 - 4:00:48 PM
Last modification on : Friday, February 26, 2021 - 3:28:06 PM
Long-term archiving on: : Friday, November 25, 2016 - 5:47:56 PM

File

termgraph.pdf
Files produced by the author(s)

Identifiers

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. ⟨10.1016/j.entcs.2008.03.034⟩. ⟨inria-00129391v3⟩

Share

Metrics

Record views

334

Files downloads

259