Intensional properties of polygraphs
<|reference_start|>Intensional properties of polygraphs: We present polygraphic programs, a subclass of Albert Burroni's polygraphs, as a computational model, showing how these objects can be seen as first-order functional programs. We prove that the model is Turing complete. We use polygraphic interpretations, a termination proof method introduced by the second author, to characterize polygraphic programs that compute in polynomial time. We conclude with a characterization of polynomial time functions and non-deterministic polynomial time functions.<|reference_end|>
@article{bonfante2007intensional,
    title={Intensional properties of polygraphs},
    author={Guillaume Bonfante, Yves Guiraud},
    journal={Electronic Notes in Theoretical Computer Science 203(1):65-77
  (2008)},
    year={2007},
    doi={10.1016/j.entcs.2008.03.034},
    archivePrefix={arXiv},
    eprint={cs/0703007},
    primaryClass={cs.LO cs.CC math.CT}
}