Abstract
In a recent work, Girard proposed a new and innovative approach to computational complexity based on the proofs-as-programs correspondence. In a previous paper, the authors showed how Girard's proposal succeeds in obtaining a new characterization of co-NL languages as a set of operators acting on a Hilbert Space. In this paper, we extend this work by showing that it is also possible to define a set of operators characterizing the class L of logarithmic space languages.
Original language | English (US) |
---|---|
Pages (from-to) | 2-21 |
Number of pages | 20 |
Journal | Information and Computation |
Volume | 248 |
DOIs | |
State | Published - Jun 1 2016 |
Externally published | Yes |
Keywords
- Complexity
- Finite automata
- Geometry of interaction
- Linear logic
- Logarithmic space
- Pointer machine
ASJC Scopus subject areas
- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics