Intensional properties of polygraphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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.
Proceedings of TERMGRAPH 2007, Electronic Notes in Computer Science (to appear), 12 pages, minor changes from previous version

Keywords

Logic in Computer Science, Computational Complexity, Category Theory, F.1.1; F.4

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/170806

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0703007
 http://arxiv.org/abs/cs/0703007
 Electronic Notes in Theoretical Computer Science 203(1):65-77 (2008)
 doi:10.1016/j.entcs.2008.03.034

Collections

arXiv