Algorithmically broad languages for polynomial time and space

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

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)

Cites Work

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

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)