Intensional properties of polygraphs
| dc.creator | Bonfante, Guillaume | |
| dc.creator | Guiraud, Yves | |
| dc.date | 2007-03-02 | |
| dc.date | 2007-11-20 | |
| dc.date.accessioned | 2026-07-07T10:07:54Z | |
| dc.date.available | 2026-07-07T10:07:54Z | |
| dc.description | 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. | |
| dc.description | Proceedings of TERMGRAPH 2007, Electronic Notes in Computer Science (to appear), 12 pages, minor changes from previous version | |
| dc.identifier | https://arxiv.org/abs/cs/0703007 | |
| dc.identifier | http://arxiv.org/abs/cs/0703007 | |
| dc.identifier | Electronic Notes in Theoretical Computer Science 203(1):65-77 (2008) | |
| dc.identifier | doi:10.1016/j.entcs.2008.03.034 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/170806 | |
| dc.subject | Logic in Computer Science | |
| dc.subject | Computational Complexity | |
| dc.subject | Category Theory | |
| dc.subject | F.1.1; F.4 | |
| dc.title | Intensional properties of polygraphs | |
| dc.type | text |