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 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4123722 (Why is no real title available?)
- Elementary complexity and geometry of interaction
- Geometry of interaction. V: Logic in the hyperfinite factor
- Interaction graphs: additives
- Interaction graphs: multiplicatives
- Linear logic and elementary time
- Multi-head finite automata: characterizations, concepts and open problems
- Nondeterministic Space is Closed under Complementation
- Normativity in logic
- On Multi-Head Finite Automata
- On non-determinacy in simple computing devices
- Some operator inequalities concerning generalized inverses
- Theory of operator algebras I.
Cited in
(6)- scientific article; zbMATH DE number 3109424 (Why is no real title available?)
- Interaction graphs: graphings
- Unary resolution: characterizing \textsc{Ptime}
- A correspondence between maximal abelian sub-algebras and linear logic fragments
- Geometry of resource interaction and Taylor-Ehrhard-Regnier expansion: \textit{a minimalist approach}
- scientific article; zbMATH DE number 6917940 (Why is no real title available?)
This page was built for publication: Logarithmic space and permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q276248)
