Programs as polygraphs: computability and complexity
Guillaume Bonfante, Yves Guiraud · arXiv (Cornell University) · 2007
Abstract – This study presents Albert Burroni’s polygraphs as an algebraic and graphical description of first-order functional programs, where functions can have many outputs. We prove that polygraphic programs form a Turing-complete computational model. Using already-known termination orders for polygraphs, we define simple programs as a special class of polygraphs equipped with a notion of polynomial interpretation. We prove that computations in a simple program have a polynomial size and conclude that simple programs compute exactly polynomial-time functions. Keywords – Polygraph, program, computability, polynomial interpretation, termination, complexity. ACM – F.1.1, F.4.1, F.4.2, F.4.3. 1