Characterizing co-NL by a group action

Clément Aubert; Thomas Seiller

doi:10.1017/S0960129514000267

Characterizing co-NL by a group action

Clément Aubert, Thomas Seiller

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

In a recent paper, Girard (2012) proposed to use his recent construction of a geometry of interaction in the hyperfinite factor (Girard 2011) 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 the non-deterministic pointer machine as a technical tool, a concrete model to compute algorithms.

Original language	English (US)
Pages (from-to)	606-638
Number of pages	33
Journal	Mathematical Structures in Computer Science
Volume	26
Issue number	4
DOIs	https://doi.org/10.1017/S0960129514000267
State	Published - May 1 2016
Externally published	Yes

ASJC Scopus subject areas

Mathematics (miscellaneous)
Computer Science Applications

Access to Document

10.1017/S0960129514000267

Cite this

@article{bea25aca3177435ca21e86e8958e3fbd,

title = "Characterizing co-NL by a group action",

abstract = "In a recent paper, Girard (2012) proposed to use his recent construction of a geometry of interaction in the hyperfinite factor (Girard 2011) 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 the non-deterministic pointer machine as a technical tool, a concrete model to compute algorithms.",

author = "Cl{\'e}ment Aubert and Thomas Seiller",

note = "Publisher Copyright: Copyright {\textcopyright} 2014 Cambridge University Press.",

year = "2016",

month = may,

day = "1",

doi = "10.1017/S0960129514000267",

language = "English (US)",

volume = "26",

pages = "606--638",

journal = "Mathematical Structures in Computer Science",

issn = "0960-1295",

publisher = "Cambridge University Press",

number = "4",

}

TY - JOUR

T1 - Characterizing co-NL by a group action

AU - Aubert, Clément

AU - Seiller, Thomas

PY - 2016/5/1

Y1 - 2016/5/1

N2 - In a recent paper, Girard (2012) proposed to use his recent construction of a geometry of interaction in the hyperfinite factor (Girard 2011) 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 the non-deterministic pointer machine as a technical tool, a concrete model to compute algorithms.

AB - In a recent paper, Girard (2012) proposed to use his recent construction of a geometry of interaction in the hyperfinite factor (Girard 2011) 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 the non-deterministic pointer machine as a technical tool, a concrete model to compute algorithms.

UR - http://www.scopus.com/inward/record.url?scp=84916910092&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84916910092&partnerID=8YFLogxK

U2 - 10.1017/S0960129514000267

DO - 10.1017/S0960129514000267

M3 - Article

AN - SCOPUS:84916910092

SN - 0960-1295

VL - 26

SP - 606

EP - 638

JO - Mathematical Structures in Computer Science

JF - Mathematical Structures in Computer Science

IS - 4

ER -

Characterizing co-NL by a group action

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this