{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T23:11:34Z","timestamp":1790637094161,"version":"4.1.0"},"reference-count":27,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,12,5]],"date-time":"2014-12-05T00:00:00Z","timestamp":1417737600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2016,5]]},"abstract":"<jats:p>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<jats:bold>co-NL<\/jats:bold>can be characterized using this new approach. We introduce the non-deterministic pointer machine as a technical tool, a concrete model to compute algorithms.<\/jats:p>","DOI":"10.1017\/s0960129514000267","type":"journal-article","created":{"date-parts":[[2014,12,5]],"date-time":"2014-12-05T09:59:04Z","timestamp":1417773544000},"page":"606-638","source":"Crossref","is-referenced-by-count":7,"title":["Characterizing<b>co-NL<\/b>by a group action"],"prefix":"10.1017","volume":"26","author":[{"given":"CL\u00c9MENT","family":"AUBERT","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"THOMAS","family":"SEILLER","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,12,5]]},"reference":[{"key":"S0960129514000267_ref17","volume-title":"C*-Algebras and Operator Theory","author":"Murphy","year":"1990"},{"key":"S0960129514000267_ref6","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-6(4:7)2010"},{"key":"S0960129514000267_ref24","volume-title":"Theory of Operator Algebras 1","author":"Takesaki","year":"2001"},{"key":"S0960129514000267_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)70271-4"},{"key":"S0960129514000267_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"S0960129514000267_ref22","unstructured":"Seiller T. (2012c) Logique dans le Facteur Hyperfini: G\u00e9ometrie de l'interaction et Complexit\u00e9, Ph.D. thesis, Universit\u00e9 de la M\u00e9diterran\u00e9e. Available at http:\/\/tel.archives-ouvertes.fr\/tel-00768403\/"},{"key":"S0960129514000267_ref19","doi-asserted-by":"crossref","unstructured":"Sch\u00f6pp U. (2007) Stratified bounded affine logic for logarithmic space. In: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science (LICS), IEEE Computer Society 411\u2013420.","DOI":"10.1109\/LICS.2007.45"},{"key":"S0960129514000267_ref15","doi-asserted-by":"crossref","unstructured":"Immerman N. (1988) Nondeterministic space is closed under complementation In: Proceedings of the Third Annual Structure in Conference on Computational Complexity (CoCo), IEEE Computer Society 112\u2013115.","DOI":"10.1109\/SCT.1988.5270"},{"key":"S0960129514000267_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37075-5_21"},{"key":"S0960129514000267_ref25","volume-title":"Theory of Operator Algebras 2","author":"Takesaki","year":"2003"},{"key":"S0960129514000267_ref2","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.75.2"},{"key":"S0960129514000267_ref14","doi-asserted-by":"crossref","unstructured":"Hofmann M. and Sch\u00f6pp U. (2009) Pointer programs and undirected reachability. In: Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science (LICS), IEEE Computer Society 133\u2013142.","DOI":"10.1109\/LICS.2009.41"},{"key":"S0960129514000267_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.12.016"},{"key":"S0960129514000267_ref5","doi-asserted-by":"crossref","unstructured":"Dal Lago U. (2005) The geometry of linear higher-order recursion In: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS), IEEE Computer Society 366\u2013375.","DOI":"10.1109\/LICS.2005.52"},{"key":"S0960129514000267_ref9","doi-asserted-by":"crossref","unstructured":"Girard J. -Y. (1989b) Towards a geometry of interaction. In: Proceedings of the AMS Conference on Categories, Logic and Computer Science 69\u2013108.","DOI":"10.1090\/conm\/092\/1003197"},{"key":"S0960129514000267_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00010-5"},{"key":"S0960129514000267_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2012.04.005"},{"key":"S0960129514000267_ref23","first-page":"96","article-title":"The method of forcing for nondeterministic automata","volume":"33","author":"Szelepsc\u00e9nyi","year":"1987","journal-title":"Bulletin of the EATCS"},{"key":"S0960129514000267_ref18","doi-asserted-by":"publisher","DOI":"10.1147\/rd.105.0388"},{"key":"S0960129514000267_ref26","volume-title":"Theory of Operator Algebras 3","author":"Takesaki","year":"2003"},{"key":"S0960129514000267_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.10.018"},{"key":"S0960129514000267_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-007-4435-6_12"},{"key":"S0960129514000267_ref3","first-page":"1","article-title":"Elementary complexity and geometry of interaction","volume":"45","author":"Baillot","year":"2001","journal-title":"Fundamenta Informaticae"},{"key":"S0960129514000267_ref12","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-11606"},{"key":"S0960129514000267_ref20","unstructured":"Seiller T. (2012a) Interaction graphs: Additives. Arxiv preprint abs\/1205.6557."},{"key":"S0960129514000267_ref4","volume-title":"A Course in Functional Analysis","author":"Conway","year":"1990"},{"key":"S0960129514000267_ref27","doi-asserted-by":"crossref","unstructured":"Terui K. (2004) Proof nets and boolean circuits. In: Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society 182\u2013191.","DOI":"10.1109\/LICS.2004.1319612"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129514000267","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,18]],"date-time":"2019-08-18T05:05:46Z","timestamp":1566104746000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129514000267\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,5]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["S0960129514000267"],"URL":"https:\/\/doi.org\/10.1017\/s0960129514000267","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,5]]}}}