An arithmetic for non-size-increasing polynomial-time computation

DOI10.1016/J.TCS.2003.10.023MaRDI QIDQ1827388zbMATH OpenOpenAlexFDO

Authors Klaus Aehlig, Ulrich Berger, Martin Hofmann, Helmut Schwichtenberg

Publication date 6 August 2004

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

Full work available at URL https://doi.org/10.1016/j.tcs.2003.10.023

zbMATH Keywords

Implicit computational complexityLambda calculusRealizabilityArithmeticHigher typesNon-size-increasing polynomial-time computation

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• An arithmetic for polynomial-time computation
• A syntactical analysis of non-size-increasing polynomial time computation
• Linear types and non-size-increasing polynomial time computation.
• A weak constructive second-order arithmetic with extraction of algorithms computable in polynomial time
• Publication:3472100

Cites work

• scientific article; zbMATH DE number 996558 (Why is no real title available?)
• scientific article; zbMATH DE number 512774 (Why is no real title available?)
• A syntactical analysis of non-size-increasing polynomial time computation
• A type system for bounded space and functional in-place update
• Higher type recursion, ramification and polynomial time
• Intrinsic reasoning about functional programs. I: First order theories
• Short proofs of normalization for the simply-typed \(\lambda\)-calculus, permutative conversions and Gödel's \(\mathbf T\)
• The strength of non-size increasing computation
• ÜBER EINE BISHER NOCH NICHT BENÜTZTE ERWEITERUNG DES FINITEN STANDPUNKTES

Cited in

(17)

• scientific article; zbMATH DE number 4139739 (Why is no real title available?)
• Proof-theoretic semantics and feasibility
• Modular inference of linear types for multiplicity-annotated arrows
• scientific article; zbMATH DE number 1848310 (Why is no real title available?)
• scientific article; zbMATH DE number 1834639 (Why is no real title available?)
• Introduction to clarithmetic. I
• An arithmetic for polynomial-time computation
• The strength of non-size increasing computation
• Implicit computation complexity in higher-order programming languages
• Linear types and non-size-increasing polynomial time computation.
• Build your own clarithmetic. I: Setup and completeness
• Extracting a DPLL algorithm
• scientific article; zbMATH DE number 67686 (Why is no real title available?)
• Algorithmically broad languages for polynomial time and space
• Propositional representation of arithmetic proofs (preliminary version)
• A syntactical analysis of non-size-increasing polynomial time computation
• A weak constructive second-order arithmetic with extraction of algorithms computable in polynomial time

This page was built for publication: An arithmetic for non-size-increasing polynomial-time computation

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