{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:58Z","timestamp":1725490258621},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540749141"},{"type":"electronic","value":"9783540749158"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74915-8_33","type":"book-chapter","created":{"date-parts":[[2007,8,24]],"date-time":"2007-08-24T05:13:35Z","timestamp":1187932415000},"page":"435-450","source":"Crossref","is-referenced-by-count":1,"title":["Correctness of Multiplicative (and Exponential) Proof Structures is NL-Complete"],"prefix":"10.1007","author":[{"given":"Paulin","family":"Jacob\u00e9 de Naurois","sequence":"first","affiliation":[]},{"given":"Virgile","family":"Mogbil","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"33_CR1","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"S.A. Cook","year":"1987","unstructured":"Cook, S.A., McKenzie, P.: Problems complete for deterministic logarithmic space. J. Algorithms\u00a08(3), 385\u2013394 (1987)","journal-title":"J. Algorithms"},{"issue":"2","key":"33_CR2","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A.K. Chandra","year":"1984","unstructured":"Chandra, A.K., Stockmeyer, L.J., Vishkin, U.: Constant depth reducibility. SIAM J. Comput.\u00a013(2), 423\u2013439 (1984)","journal-title":"SIAM J. Comput."},{"key":"33_CR3","unstructured":"Danos, V.: Une application de la logique lin\u00e9aire \u00e0 l\u2019\u00e9tude des processus de normalisation (principalement de \u03bb-calcul). PhD thesis, Universit\u00e9 Denis Diderot, Paris 7 (1990)"},{"issue":"3","key":"33_CR4","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF01622878","volume":"28","author":"V. Danos","year":"1989","unstructured":"Danos, V., Regnier, L.: The structure of multiplicatives. Archive for Mathematical Logic\u00a028(3), 181\u2013203 (1989)","journal-title":"Archive for Mathematical Logic"},{"issue":"1","key":"33_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(87)90045-4","volume":"50","author":"J.-Y. Girard","year":"1987","unstructured":"Girard, J.-Y.: Linear logic. Theoretical Computer Science\u00a050(1), 1\u2013102 (1987)","journal-title":"Theoretical Computer Science"},{"issue":"1\u20132","key":"33_CR6","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0304-3975(99)00299-6","volume":"254","author":"S. Guerrini","year":"2001","unstructured":"Guerrini, S., Masini, A.: Parsing MELL proof nets. Theoretical Computer Science\u00a0254(1\u20132), 317\u2013335 (2001)","journal-title":"Theoretical Computer Science"},{"key":"33_CR7","first-page":"454","volume-title":"Proc. of the annual Symp. on Logic in Computer Science (LICS 1999)","author":"S. Guerrini","year":"1999","unstructured":"Guerrini, S.: Correctness of multiplicative proof nets is linear. In: Proc. of the annual Symp. on Logic in Computer Science (LICS 1999), pp. 454\u2013463. IEEE Computer Society Press, Los Alamitos (1999)"},{"issue":"5","key":"33_CR8","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput.\u00a017(5), 935\u2013938 (1988)","journal-title":"SIAM J. Comput."},{"key":"33_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01683259","volume":"10","author":"N.D. Jones","year":"1976","unstructured":"Jones, N.D., Lien, Y.E., Laaser, W.T.: New problems complete for nondeterministic logspace. Mathematical Syst. Theory\u00a010, 1\u201317 (1976)","journal-title":"Mathematical Syst. Theory"},{"key":"33_CR10","unstructured":"Jenner, B., Lange, K.-J., McKenzie, P.: Tree isomorphism and some other complete problems for deterministic logspace. DIRO 1059, Univ. de Montr\u00e9al (1997)"},{"key":"33_CR11","first-page":"200","volume-title":"Proc. of the annual Symp. on Logic in Computer Science (LICS 1992)","author":"M.I. Kanovich","year":"1992","unstructured":"Kanovich, M.I.: Horn programming in linear logic is NP-complete. In: Proc. of the annual Symp. on Logic in Computer Science (LICS 1992), pp. 200\u2013210. IEEE Computer Society Press, Los Alamitos (1992)"},{"key":"33_CR12","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1017\/CBO9780511629150.012","volume-title":"Advances in Linear Logic","author":"Y. Lafont","year":"1995","unstructured":"Lafont, Y.: From proof-nets to interaction nets. In: Girard, J.-Y., Lafont, Y., Regnier, L. (eds.) Advances in Linear Logic, vol.\u00a0222, pp. 225\u2013247. Cambridge University Press, Cambridge (1995)"},{"key":"33_CR13","unstructured":"Mairson, H.G.: Normalization bounds for multiplicative linear logic are axiom-sensitive. In: GEOCAL 2006 Workshop of Implicit Computational Complexity. Slides available at http:\/\/www-lipn.univ-paris13.fr\/~baillot\/GEOCAL06\/SLIDES\/Mairson.pdf"},{"key":"33_CR14","series-title":"London Mathematical Society Lecture Notes Series","volume-title":"A topological correctness criterion for non-commutative logic","author":"P.-A. Melli\u00e8s","year":"2004","unstructured":"Melli\u00e8s, P.-A.: A topological correctness criterion for non-commutative logic. London Mathematical Society Lecture Notes Series, vol.\u00a0316. Cambridge University Press, Cambridge (2004)"},{"key":"33_CR15","first-page":"181","volume-title":"Proc. of the annual Symp. on Logic in Computer Science (LICS 2000)","author":"A. Murawski","year":"2000","unstructured":"Murawski, A., Ong, L.: Dominator trees and fast verification of proof nets. In: Proc. of the annual Symp. on Logic in Computer Science (LICS 2000), pp. 181\u2013191. IEEE Computer Society Press, Los Alamitos (2000)"},{"issue":"3","key":"33_CR16","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1145\/1149114.1149116","volume":"7","author":"A. Murawski","year":"2006","unstructured":"Murawski, A., Ong, L.: Fast verification of MLL proof nets via IMLL. ACM Trans. Comput. Logic\u00a07(3), 473\u2013498 (2006)","journal-title":"ACM Trans. Comput. Logic"},{"key":"33_CR17","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1145\/1060590.1060647","volume-title":"STOC","author":"O. Reingold","year":"2005","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: Gabow, H.N., Fagin, R. (eds.) STOC, pp. 376\u2013385. ACM, New York (2005)"},{"key":"33_CR18","first-page":"96","volume":"33","author":"R. Szelepcs\u00e9nyi","year":"1987","unstructured":"Szelepcs\u00e9nyi, R.: The method of forcing for nondeterministic automata. Bulletin of the EATCS\u00a033, 96\u201399 (1987)","journal-title":"Bulletin of the EATCS"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74915-8_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T22:26:44Z","timestamp":1684016804000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74915-8_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540749141","9783540749158"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74915-8_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}