Algorithmically broad languages for polynomial time and space

DOI10.1007/978-3-030-88853-4_23MaRDI QIDQ2148807OpenAlexFDO

Authors Daniel M. Leivant

Publication date 24 June 2022

Full work available at URL https://doi.org/10.1007/978-3-030-88853-4_23

zbMATH Keywords

ramificationimperative programmingbundlesvariantsPSpacenon-size-increaseparameterless proceduresPTime

Mathematics Subject Classification ID

Logic in computer science (03B70)

Recommendations

• An imperative language characterizing PTIME algorithms
• scientific article; zbMATH DE number 1302629
• Light affine logic as a programming language: a first contribution
• Bounded linear logic: A modular approach to polynomial-time computability
• scientific article; zbMATH DE number 176206

Cites work

• scientific article; zbMATH DE number 439891 (Why is no real title available?)
• scientific article; zbMATH DE number 3740740 (Why is no real title available?)
• scientific article; zbMATH DE number 3480091 (Why is no real title available?)
• scientific article; zbMATH DE number 3572133 (Why is no real title available?)
• scientific article; zbMATH DE number 3574936 (Why is no real title available?)
• scientific article; zbMATH DE number 2079048 (Why is no real title available?)
• scientific article; zbMATH DE number 1499100 (Why is no real title available?)
• scientific article; zbMATH DE number 1556014 (Why is no real title available?)
• scientific article; zbMATH DE number 806743 (Why is no real title available?)
• scientific article; zbMATH DE number 806752 (Why is no real title available?)
• A characterization of alternating log time by ramified recurrence
• A higher-order characterization of probabilistic polynomial time
• A new recursion-theoretic characterization of the polytime functions
• A recursion-theoretic approach to NP
• An arithmetic for non-size-increasing polynomial-time computation
• Arithmetical hierarchy and complexity of computation
• Automatic synthesis of typed \(\Lambda\)-programs on term algebras
• Bernays and Set Theory
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
• Characterizing NC with tier 0 pointers
• Characterizing PSPACE with pointers
• Classes of Predictably Computable Functions
• Evolving Graph-Structures and Their Implicit Computational Complexity
• Implicit characterizations of FPTIME and NC revisited
• Linear types and non-size-increasing polynomial time computation.
• Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time
• On the computational complexity of imperative programming languages
• Primitive recursion in the abstract
• Tight worst-case bounds for polynomial loop programs

Cited in

(2)

• A new complete language for DSPACE(log n)
• A Polynomial-Time Algorithm for Computing Finite-Makespan Controllable Sublanguages

This page was built for publication: Algorithmically broad languages for polynomial time and space

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