Intensional properties of polygraphs

DOI10.1016/J.ENTCS.2008.03.034MaRDI QIDQ2870314zbMATH OpenOpenAlexFDO

Authors Guillaume Bonfante, Yves Guiraud

Publication date 17 January 2014

Published in Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0703007

zbMATH Keywords

complexitypolygraphpolygraphic interpretationpolygraphic programtermination

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Functional programming and lambda calculus (68N18)

Abstract: 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.

Recommendations

• Polygraph arrangements
• On the first Zagreb index of polygraphs
• Polygraphs of finite derivation type
• The matching polynomial of a polygraph
• Distance-related invariants on polygraphs
• scientific article; zbMATH DE number 1924513
• On ``The matching polynomial of a polygraph
• In search of the magic lasso: the truth about the polygraph

Cites work

• Algorithms with polynomial interpretation termination proof
• Essentials of term graph rewriting
• Higher-dimensional word problems with applications to equational logic
• scientific article; zbMATH DE number 1348481 (Why is no real title available?)
• scientific article; zbMATH DE number 1924513 (Why is no real title available?)
• scientific article; zbMATH DE number 786495 (Why is no real title available?)
• Intensional properties of polygraphs
• Tailoring recursion for complexity
• Termination orders for three-dimensional rewriting
• The three dimensions of proofs
• Towards an algebraic theory of Boolean circuits.

Cited in

(5)

• In search of the magic lasso: the truth about the polygraph
• On the first Zagreb index of polygraphs
• Intensional properties of polygraphs
• Polygraphic programs and polynomial-time functions
• Termination orders for 3-polygraphs

This page was built for publication: Intensional properties of polygraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2870314)