Published in

Elsevier, Information and Computation, (248), p. 2-21, 2016

DOI: 10.1016/j.ic.2014.01.018

Links

Tools

Export citation

Search in Google Scholar

Logarithmic Space and Permutations

Journal article published in 2013 by Clément Aubert ORCID, Thomas Seiller ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Orange circle
Postprint: archiving restricted
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

Accepté pour publication dans le numéro spécial consacré à la complexité implicite de Information & Computation. ; 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.