Characterizingco-NLby a group action
From MaRDI portal
Publication:5741572
DOI10.1017/S0960129514000267zbMATH Open1362.68084arXiv1209.3422OpenAlexW2044971924MaRDI QIDQ5741572FDOQ5741572
Authors: Clément Aubert, Thomas Seiller 
Publication date: 28 July 2016
Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1209.3422
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
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Proof-theoretic aspects of linear logic and other substructural logics (03F52)
Cites Work
- Title not available (Why is that?)
- The standard form of von Neumann algebras.
- Computational Complexity
- Linear logic and elementary time
- Soft linear logic and polynomial time
- Normativity in Logic
- Geometry of interaction. V: Logic in the hyperfinite factor
- On Multi-Head Finite Automata
- Interaction graphs: multiplicatives
- Pure Pointer Programs and Tree Isomorphism
Cited In (7)
- Unary Resolution: Characterizing Ptime
- Geometry of resource interaction and Taylor–Ehrhard–Regnier expansion: a minimalist approach
- Interaction graphs: additives
- A correspondence between maximal abelian sub-algebras and linear logic fragments
- Interaction graphs: graphings
- Rule-Following and the Limits of Formalization: Wittgenstein’s Considerations Through the Lens of Logic
- Title not available (Why is that?)
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)
