Skip to Main content Skip to Navigation
Journal articles

Polygraphic programs and polynomial-time functions

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 study the computational model of polygraphs. For that, we consider polygraphic programs, a subclass of these objects, as a formal description of first-order functional programs. We explain their semantics and prove that they form a Turing-complete computational model. Their algebraic structure is used by analysis tools, called polygraphic interpretations, for complexity analysis. In particular, we delineate a subclass of polygraphic programs that compute exactly the functions that are Turing-computable in polynomial time.
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Yves Guiraud Connect in order to contact the contributor
Submitted on : Tuesday, May 12, 2009 - 11:52:30 AM
Last modification on : Wednesday, January 26, 2022 - 3:07:55 AM
Long-term archiving on: : Saturday, November 26, 2016 - 8:33:44 AM


Files produced by the author(s)




Guillaume Bonfante, Yves Guiraud. Polygraphic programs and polynomial-time functions. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2009, 5 (2:14), pp.1-37. ⟨10.2168/LMCS-5(2:14)2009⟩. ⟨inria-00122932v3⟩



Record views


Files downloads