Polygraphic programs and polynomial-time functions

Guillaume Bonfante; Yves Guiraud

doi:10.2168/LMCS-5(2:14)2009

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

lmcs:764 - Logical Methods in Computer Science, June 3, 2009, Volume 5, Issue 2 - https://doi.org/10.2168/LMCS-5(2:14)2009

Polygraphic programs and polynomial-time functionsArticle

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.

Comment: Logical Methods in Computer Science (to appear), 37 pages, 1 colour picture, corrected typos

https://doi.org/10.2168/LMCS-5(2:14)2009

Source: arXiv.org:cs.LO/0701032

Volume: Volume 5, Issue 2

Published on: June 3, 2009

Imported on: January 5, 2007

Keywords: Computer Science - Logic in Computer Science, Computer Science - Computational Complexity, Mathematics - Category Theory, F.1.1, F.4

Licence: arXiv.org - Non-exclusive license to distribute

Funding:

Source : OpenAIRE Graph