An imperative language characterizing PTIME algorithms

zbMATH Open1429.68083MaRDI QIDQ5213552FDOQ5213552

Authors: Yoann Marquer, Pierre Valarcher 

Publication date: 3 February 2020

Recommendations

• LOGSPACE and PTIME characterized by programming languages
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
• On the computational complexity of imperative programming languages
• Some Programming Languages for Logspace and Ptime
• A representation theorem for primitive recursive algorithms

Mathematics Subject Classification ID

Theory of programming languages (68N15) Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of algorithms (68W01)

Cited In (3)

• Axiomatization and characterization of BSP algorithms
• LOGSPACE and PTIME characterized by programming languages
• Implicit characterizations of FPTIME and NC revisited

This page was built for publication: An imperative language characterizing PTIME algorithms

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