Complete and tractable machine-independent characterizations of second-order polytime

DOI10.1007/978-3-030-99253-8_19arXiv2208.14739OpenAlexW4226074176MaRDI QIDQ6181938

Bruce M. Kapron, Jean-Yves Marion, Romain Péchoux, Emmanuel Hainry

Publication date: 23 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

polynomial timesecond-ordersafe recursiontype 2basic feasible functionalstiering

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Higher-order interpretations and program complexity
• Quasi-interpretations. A way to control resources
• Complexity for type-2 relations
• Light types for polynomial time computation in lambda calculus
• Linear logic by levels and bounded time complexity
• Automata on infinite words. Ecole de Printemps d'Informatique Théorique, Le Mont Dore, May 14-18, 1984
• A new recursion-theoretic characterization of the polytime functions
• Polynomial and abstract subrecursive classes
• Light linear logic
• The relative complexity of NP search problems
• Type-two polynomial-time and restricted lookahead
• Characterizing polynomial time complexity of stream programs using interpretations
• On characterizations of the basic feasible functionals, Part I
• δ-Complete Decision Procedures for Satisfiability over the Reals
• Complexity Theory for Operators in Analysis
• Size-Change Termination and Bound Analysis
• FUNCTIONAL PEARL Linear lambda calculus and PTIME-completeness
• Polynomial Running Times for Polynomial-Time Oracle Machines
• A tier-based typed programming language characterizing Feasible Functionals
• The size-change principle for program termination

This page was built for publication: Complete and tractable machine-independent characterizations of second-order polytime