Logarithmic space and permutations

DOI10.1016/J.IC.2014.01.018zbMATH Open1339.68095arXiv1301.3189OpenAlexW2137388237MaRDI QIDQ276248FDOQ276248

Authors: Clément Aubert, Thomas Seiller 

Publication date: 3 May 2016

Published in: Information and Computation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1301.3189

Recommendations

• Characterizingco-NLby a group action
• LOGSPACE and PTIME characterized by programming languages
• scientific article; zbMATH DE number 6917940
• Unification and Logarithmic Space
• Logic programming and logarithmic space

zbMATH Keywords

complexityfinite automatalinear logiclogarithmic spacegeometry of interactionpointer machine

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Cites Work

• Theory of operator algebras I.
• Linear logic and elementary time
• On non-determinacy in simple computing devices
• Elementary complexity and geometry of interaction
• Nondeterministic Space is Closed under Complementation
• Title not available (Why is that?)
• Multi-head finite automata: characterizations, concepts and open problems
• Normativity in logic
• Geometry of interaction. V: Logic in the hyperfinite factor
• On Multi-Head Finite Automata
• Interaction graphs: multiplicatives
• Some operator inequalities concerning generalized inverses
• Interaction graphs: additives

Cited In (6)

• A correspondence between maximal abelian sub-algebras and linear logic fragments
• Interaction graphs: graphings
• Geometry of resource interaction and Taylor-Ehrhard-Regnier expansion: \textit{a minimalist approach}
• Title not available (Why is that?)
• Title not available (Why is that?)
• Unary resolution: characterizing \textsc{Ptime}

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)