Guillaume Bonfante ; Yves Guiraud - Polygraphic programs and polynomial-time functions

lmcs:764 - Logical Methods in Computer Science, June 3, 2009, Volume 5, Issue 2 -
Polygraphic programs and polynomial-time functions

Authors: Guillaume Bonfante ; Yves Guiraud

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.

Volume: Volume 5, Issue 2
Published on: June 3, 2009
Accepted on: June 25, 2015
Submitted on: January 5, 2007
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Mathematics - Category Theory,F.1.1,F.4


Consultation statistics

This page has been seen 219 times.
This article's PDF has been downloaded 168 times.