Algorithmically broad languages for polynomial time and space

DOI10.1007/978-3-030-88853-4_23OpenAlexW3204615532MaRDI QIDQ2148807

Daniel 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)

Cites Work

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