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

https://hal.inria.fr/inria-00122932
Contributor : Yves Guiraud <>
Submitted on : Tuesday, May 12, 2009 - 11:52:30 AM
Last modification on : Friday, February 26, 2021 - 3:28:06 PM
Long-term archiving on: : Saturday, November 26, 2016 - 8:33:44 AM

File

polypoly.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

493

Files downloads

737