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.


    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
    Funding:
      Source : OpenAIRE Graph
    • Invariants algébriques des systèmes informatiques; Funder: French National Research Agency (ANR); Code: ANR-05-BLAN-0267

    3 Documents citing this article

    Consultation statistics

    This page has been seen 946 times.
    This article's PDF has been downloaded 248 times.