Intensional properties of polygraphs

Details Intensional properties of polygraphs Intensional properties of polygraphs

2007-03-02

arxiv.org/abs/cs/0703007v2

Electronic Notes in Theoretical Computer Science 203(1):65-77 (2008)

Computer Science

Logic in Computer Science

Proceedings of TERMGRAPH 2007, Electronic Notes in Computer Science (to appear), 12 pages, minor changes from previous version

Scientific paper

10.1016/j.entcs.2008.03.034

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.

Affiliated with

Also associated with

No associations

Rating

Intensional properties of polygraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Intensional properties of polygraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Intensional properties of polygraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-284479