Some Programming Languages for Logspace and Ptime

DOI10.1007/11784180_8zbMATH Open1236.68074OpenAlexW1488933458MaRDI QIDQ3623925FDOQ3623925

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

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

Mathematics Subject Classification ID

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

Cited In (11)

• Computation by interaction for space-bounded functional programming
• Ramified Corecurrence and Logspace
• Programming languages capturing complexity classes
• 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
• Title not available (Why is that?)
• Logspace and logtime leaf languages
• Term rewriting characterisation of LOGSPACE for finite and infinite data
• A predicative and decidable characterization of the polynomial classes of languages
• Read/write factorizable programs
• 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)