Bonfante, Guillaume and Guiraud, Yves - 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: Bonfante, Guillaume and Guiraud, Yves

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.


Source : oai:arXiv.org:cs.LO/0701032
DOI : 10.2168/LMCS-5(2:14)2009
Volume: Volume 5, Issue 2
Published on: June 3, 2009
Submitted on: January 5, 2007
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Mathematics - Category Theory,F.1.1,F.4


Share

Consultation statistics

This page has been seen 40 times.
This article's PDF has been downloaded 53 times.