Polygraphic programs and polynomial-time functions
<|reference_start|>Polygraphic programs and polynomial-time functions: 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.<|reference_end|>
@article{bonfante2007polygraphic,
    title={Polygraphic programs and polynomial-time functions},
    author={Guillaume Bonfante, Yves Guiraud},
    journal={Logical Methods in Computer Science, Volume 5, Issue 2 (June 3,
  2009) lmcs:764},
    year={2007},
    doi={10.2168/LMCS-5(2:14)2009},
    archivePrefix={arXiv},
    eprint={cs/0701032},
    primaryClass={cs.LO cs.CC math.CT}
}