Hal will be stopped for maintenance from friday on june 10 at 4pm until monday june 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Some programming languages for LOGSPACE and PTIME

Guillaume Bonfante 1
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We propose two characterizations of complexity classes by means of programming languages. The first concerns Logspace while the second leads to Ptime. This latter characterization shows that adding a choice command to a Ptime language (the language WHILE of Jones) may not necessarily provide NPtime computations. The result is close to Cook who used “auxiliary push-down automata”. Logspace is obtained through a decidable mechanism of tiering. It is based on an analysis of deforestation due to Wadler in. We get also a characterization of NLogspace.
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/inria-00105744
Contributor : Guillaume Bonfante Connect in order to contact the contributor
Submitted on : Thursday, October 12, 2006 - 11:40:29 AM
Last modification on : Friday, February 4, 2022 - 3:31:24 AM
Long-term archiving on: : Thursday, September 20, 2012 - 11:45:24 AM

Identifiers

  • HAL Id : inria-00105744, version 1

Collections

Citation

Guillaume Bonfante. Some programming languages for LOGSPACE and PTIME. 11th International Conference on Algebraic Methodology and Software Technology - AMAST'06, Jul 2006, Kuresaare/Estonie. ⟨inria-00105744⟩

Share

Metrics

Record views

97

Files downloads

241