Some Programming Languages for Logspace and Ptime

DOI10.1007/11784180_8MaRDI QIDQ3623925zbMATH OpenOpenAlexFDO

Authors Guillaume Bonfante

Publication date 28 April 2009

Published in Algebraic Methodology and Software Technology (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/inria-00105744/file/bonfante.pdf

Mathematics Subject Classification ID

Theory of programming languages (68N15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• LOGSPACE and PTIME characterized by programming languages
• Programming languages capturing complexity classes
• Logic programming and logarithmic space
• Logical and schematic characterization of complexity classes
• A predicative and decidable characterization of the polynomial classes of languages

Cited in

(11)

• Computation by interaction for space-bounded functional programming
• Programming languages capturing complexity classes
• Read/write factorizable programs
• A predicative and decidable characterization of the polynomial classes of languages
• Logspace and logtime leaf languages
• LOGSPACE and PTIME characterized by programming languages
• The power of non-determinism in higher-order implicit complexity. Characterising complexity classes using non-deterministic cons-free programming
• Ramified Corecurrence and Logspace
• Term rewriting characterisation of LOGSPACE for finite and infinite data
• scientific article; zbMATH DE number 7453191 (Why is no real title available?)
• An imperative language characterizing PTIME algorithms

This page was built for publication: Some Programming Languages for Logspace and Ptime

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