Characterizing co-NL by a group action. (5th December 2014)
- Record Type:
- Journal Article
- Title:
- Characterizing co-NL by a group action. (5th December 2014)
- Main Title:
- Characterizing co-NL by a group action
- Authors:
- AUBERT, CLÉMENT
SEILLER, THOMAS - Abstract:
- Abstract : In a recent paper, Girard (2012 ) proposed to use his recent construction of a geometry of interaction in the hyperfinite factor (Girard2011 ) 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 classco-NL can be characterized using this new approach. We introduce the non-deterministic pointer machine as a technical tool, a concrete model to compute algorithms.
- Is Part Of:
- Mathematical structures in computer science. Volume 26:Number 4(2016)
- Journal:
- Mathematical structures in computer science
- Issue:
- Volume 26:Number 4(2016)
- Issue Display:
- Volume 26, Issue 4 (2016)
- Year:
- 2016
- Volume:
- 26
- Issue:
- 4
- Issue Sort Value:
- 2016-0026-0004-0000
- Page Start:
- 606
- Page End:
- 638
- Publication Date:
- 2014-12-05
- Subjects:
- Computer science -- Mathematics -- Periodicals
004.015105 - Journal URLs:
- http://journals.cambridge.org/action/displayJournal?jid=MSC ↗
- DOI:
- 10.1017/S0960129514000267 ↗
- Languages:
- English
- ISSNs:
- 0960-1295
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library HMNTS - ELD Digital store
- Ingest File:
- 919.xml