Polygraphic programs and polynomial-time functions

DOI10.2168/LMCS-5(2:14)2009MaRDI QIDQ3636813zbMATH OpenFDO

Authors Guillaume Bonfante, Yves Guiraud

Publication date 30 June 2009

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0701032

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18)

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.

Recommendations

• Intensional properties of polygraphs
• A foundational delineation of poly-time
• scientific article; zbMATH DE number 1696756
• A new order-theoretic characterisation of the polytime computable functions
• scientific article; zbMATH DE number 1342224

Cited in

(7)

• scientific article; zbMATH DE number 3915627 (Why is no real title available?)
• scientific article; zbMATH DE number 782052 (Why is no real title available?)
• A Note on The Functions Which Are Not Polynomial Time Computable From Their Graphs
• Polynomial algorithms for the synthesis of bounded nets
• Turing-completeness of polymorphic stream equation systems
• Data Structures for Topologically Sound Higher-Dimensional Diagram Rewriting
• Termination of rewriting on reversible Boolean circuits as a free 3-category problem

This page was built for publication: Polygraphic programs and polynomial-time functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3636813)