Characterizingco-NLby a group action

DOI10.1017/S0960129514000267zbMATH Open1362.68084OpenAlexW2044971924MaRDI QIDQ5741572FDOQ5741572

Authors Clément Aubert, Thomas Seiller

Publication date 28 July 2016

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

geometry of interactioncoNLnondeterministic pointer 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)

Abstract: In a recent paper, Girard proposes to use his recent construction of a geometry of interaction in the hyperfinite factor in an innovative way to characterize complexity classes. We begin by giving a detailed explanation of both the choices and the motivations of Girard's definitions. We then provide a complete proof that the complexity class co-NL can be characterized using this new approach. We introduce as a technical tool the non-deterministic pointer machine, a concrete model to computes algorithms.

Recommendations

• Co-actions of groups
• On structure of cogroups
• A characterization of a coaction reduced to that of a closed subgroup
• scientific article; zbMATH DE number 3918597
• Coarse structures and group actions
• scientific article; zbMATH DE number 2203334
• Partial group (co)actions of Hopf group coalgebras
• Actions of cofinite groups on cofinite graphs
• Duality for groupoid (co)actions.
• A cocycle construction for groups

Cites work

• scientific article; zbMATH DE number 47995 (Why is no real title available?)
• Computational Complexity
• Geometry of interaction. V: Logic in the hyperfinite factor
• Interaction graphs: multiplicatives
• Linear logic and elementary time
• Normativity in logic
• On Multi-Head Finite Automata
• Pure Pointer Programs and Tree Isomorphism
• Soft linear logic and polynomial time
• The standard form of von Neumann algebras.

Cited in

(8)

• Logarithmic space and permutations
• Interaction graphs: graphings
• Unary resolution: characterizing \textsc{Ptime}
• Rule-following and the limits of formalization: Wittgenstein's considerations through the lens of logic
• Interaction graphs: additives
• 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: Characterizingco-NLby a group action

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741572)