{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:20:17Z","timestamp":1725852017214},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662496299"},{"type":"electronic","value":"9783662496305"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49630-5_22","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T05:04:32Z","timestamp":1458536672000},"page":"373-389","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Unary Resolution: Characterizing Ptime"],"prefix":"10.1007","author":[{"given":"Cl\u00e9ment","family":"Aubert","sequence":"first","affiliation":[]},{"given":"Marc","family":"Bagnol","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Seiller","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"22_CR1","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/S0019-9958(68)91087-5","volume":"13","author":"AV Aho","year":"1968","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: Time and tape complexity of pushdown automaton languages. Inform. Control 13(3), 186\u2013206 (1968)","journal-title":"Inform. Control"},{"key":"22_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/978-3-319-08918-8_6","volume-title":"Rewriting and Typed Lambda Calculi","author":"C Aubert","year":"2014","unstructured":"Aubert, C., Bagnol, M.: Unification and logarithmic space. In: Dowek, G. (ed.) RTA-TLCA 2014. LNCS, vol. 8560, pp. 77\u201392. Springer, Heidelberg (2014)"},{"key":"22_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/978-3-319-12736-1_3","volume-title":"Programming Languages and Systems","author":"C Aubert","year":"2014","unstructured":"Aubert, C., Bagnol, M., Pistone, P., Seiller, T.: Logic programming and logarithmic space. In: Garrigue, J. (ed.) APLAS 2014. LNCS, vol. 8858, pp. 39\u201357. Springer, Heidelberg (2014)"},{"key":"22_CR4","unstructured":"Aubert, C., Bagnol, M., Seiller, T.: Memoization for unary logic programming: Characterizing ptime. Research Report RR-8796, INRIA (2015). \n                      https:\/\/hal.archives-ouvertes.fr\/hal-01107377"},{"issue":"4","key":"22_CR5","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1017\/S0960129514000267","volume":"26","author":"CL\u00c9MENT AUBERT","year":"2014","unstructured":"Aubert, C., Seiller, T.: Characterizing co-NL by a group action. In: MSCS (FirstView), pp. 1\u201333, December 2014","journal-title":"Mathematical Structures in Computer Science"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.ic.2014.01.018","volume":"248","author":"Cl\u00e9ment Aubert","year":"2016","unstructured":"Aubert, C., Seiller, T.: Logarithmic space and permutations. Inf. Comput. Spec. Issue Implicit Comput. Complex. (2015). doi: \n                      10.1016\/j.ic.2014.01.018","journal-title":"Information and Computation"},{"key":"22_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172752","volume-title":"Term rewriting and all that","author":"F Baader","year":"1998","unstructured":"Baader, F., Nipkow, T.: Term rewriting and all that. CUP, Cambridge (1998)"},{"key":"22_CR8","unstructured":"Bagnol, M.: On the Resolution Semiring. Ph.D. thesis, Aix-Marseille Universit\u00e9 - Institut de Math\u00e9matiques de Marseille (2014). \n                      https:\/\/hal.archives-ouvertes.fr\/tel-01215334"},{"issue":"2","key":"22_CR9","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/j.tcs.2009.09.015","volume":"411","author":"P Baillot","year":"2010","unstructured":"Baillot, P., Mazza, D.: Linear logic by levels and bounded time complexity. Theoret. Comput. Sci. 411(2), 470\u2013503 (2010)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"22_CR10","first-page":"1","volume":"45","author":"P Baillot","year":"2001","unstructured":"Baillot, P., Pedicini, M.: Elementary complexity and geometry of interaction. Fund. Inform. 45(1\u20132), 1\u201331 (2001)","journal-title":"Fund. Inform."},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Baillot, P., Terui, K.: Light types for polynomial time computation in lambda-calculus. In: LICS, pp. 266\u2013275. IEEE Computer Society (2004)","DOI":"10.1109\/LICS.2004.1319621"},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01201998","volume":"2","author":"SJ Bellantoni","year":"1992","unstructured":"Bellantoni, S.J., Cook, S.A.: A new recursion-theoretic characterization of the polytime functions. Comput. Complex. 2, 97\u2013110 (1992)","journal-title":"Comput. Complex."},{"key":"22_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4204\/EPTCS.151.1","volume":"151","author":"Arnaud Carayol","year":"2014","unstructured":"Carayol, A., Hague, M.: Saturation algorithms for model-checking pushdown systems. In: \u00c9sik, Z., F\u00fcl\u00f6p, Z. (eds.), Proceedings 14th International Conference on Automata and Formal Languages, AFL 2014, Szeged, Hungary, May 27\u201329, 2014. EPTCS, vol. 151, pp. 1\u201324 (2014)","journal-title":"Electronic Proceedings in Theoretical Computer Science"},{"key":"22_CR14","unstructured":"Caucal, D.: R\u00e9critures suffixes de mots. Research Report RR-0871, INRIA (1988). \n                      https:\/\/hal.inria.fr\/inria-00075683"},{"key":"22_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/3-540-52590-4_42","volume-title":"CAAP \u201990","author":"D Caucal","year":"1990","unstructured":"Caucal, D.: On the regular structure of prefix rewriting. In: Arnold, A. (ed.) CAAP \u201990. LNCS, vol. 431, pp. 87\u2013102. Springer, Heidelberg (1990)"},{"issue":"1","key":"22_CR16","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"SA Cook","year":"1971","unstructured":"Cook, S.A.: Characterizations of pushdown machines in terms of time-bounded computers. J. ACM 18(1), 4\u201318 (1971)","journal-title":"J. ACM"},{"key":"22_CR17","unstructured":"Cook, S.A.: Linear time simulation of deterministic two-way pushdown automata. In: IFIP Congress (1), pp. 75\u201380. North-Holland (1971)"},{"key":"22_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-642-31485-8_3","volume-title":"Lectures on Logic and Computation","author":"U Dal Lago","year":"2012","unstructured":"Dal Lago, U.: A short introduction to implicit computational complexity. In: Bezhanishvili, N., Goranko, V. (eds.) ESSLLI 2010 and ESSLLI 2011. LNCS, vol. 7388, pp. 89\u2013109. Springer, Heidelberg (2012)"},{"key":"22_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-642-11957-6_12","volume-title":"Programming Languages and Systems","author":"U Lago Dal","year":"2010","unstructured":"Dal Lago, U., Sch\u00f6pp, U.: Functional programming in sublinear space. In: Gordon, A.D. (ed.) ESOP 2010. LNCS, vol. 6012, pp. 205\u2013225. Springer, Heidelberg (2010)"},{"key":"22_CR20","unstructured":"Danos, V.: La Logique Lin\u00e9aire appliqu\u00e9e \u00e1 l\u2019\u00e9tude de divers processus de normalisation (principalement du \n                      \n                        \n                      \n                      $$\\lambda $$\n                    -calcul). Ph.D. thesis, Universit Paris VII (1990)"},{"issue":"1","key":"22_CR21","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0890-5401(03)00010-5","volume":"183","author":"V Danos","year":"2003","unstructured":"Danos, V., Joinet, J.B.: Linear logic and elementary time. Inf. Comput. 183(1), 123\u2013137 (2003)","journal-title":"Inf. Comput."},{"issue":"3","key":"22_CR22","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/502807.502810","volume":"33","author":"E Dantsin","year":"2001","unstructured":"Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and expressive power of logic programming. ACM Comput. Surv. 33(3), 374\u2013425 (2001)","journal-title":"ACM Comput. Surv."},{"issue":"1","key":"22_CR23","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0743-1066(84)90022-0","volume":"1","author":"C Dwork","year":"1984","unstructured":"Dwork, C., Kanellakis, P.C., Mitchell, J.C.: On the sequential nature of unification. J. Log. Program. 1(1), 35\u201350 (1984)","journal-title":"J. Log. Program."},{"issue":"2","key":"22_CR24","doi-asserted-by":"publisher","first-page":"18:1","DOI":"10.1145\/2159531.2159540","volume":"13","author":"M Gaboardi","year":"2012","unstructured":"Gaboardi, M., Marion, J.Y., Rocca Della Rocca, S.: An implicit characterization of pspace. ACM Trans. Comput. Log. 13(2), 18:1\u201318:36 (2012)","journal-title":"ACM Trans. Comput. Log."},{"issue":"1","key":"22_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(87)90045-4","volume":"50","author":"JY Girard","year":"1987","unstructured":"Girard, J.Y.: Linear logic. Theoret. Comput. Sci. 50(1), 1\u2013101 (1987)","journal-title":"Theoret. Comput. Sci."},{"key":"22_CR26","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/S0049-237X(08)70271-4","volume":"127","author":"JY Girard","year":"1989","unstructured":"Girard, J.Y.: Geometry of interaction 1: Interpretation of system F. Stud. Logic Found. Math. 127, 221\u2013260 (1989)","journal-title":"Stud. Logic Found. Math."},{"key":"22_CR27","doi-asserted-by":"crossref","unstructured":"Girard, J.Y.: Towards a geometry of interaction. In: Gray, J.W., Scedrov, A. (eds.) Proceedings of the AMS Conference on Categories, Logic and Computer Science. Categories in Computer Science and Logic, vol. 92, pp. 69\u2013108. AMS (1989)","DOI":"10.1090\/conm\/092\/1003197"},{"key":"22_CR28","doi-asserted-by":"crossref","unstructured":"Girard, J.Y.: Geometry of interaction III: accommodating the additives. In: Girard, J.Y., Lafont, Y., Regnier, L. (eds.) Advances in Linear Logic, pp. 329\u2013389. No. 222 in London Mathematical Society Lecture Note Series, CUP, June 1995","DOI":"10.1017\/CBO9780511629150.017"},{"key":"22_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/3-540-60178-3_83","volume-title":"Logic and Computational Complexity","author":"JY Girard","year":"1995","unstructured":"Girard, J.Y.: Light linear logic. In: Leivant, D. (ed.) Logic and Computational Complexity. LNCS, vol. 960, pp. 145\u2013176. Springer, Heidelberg (1995)"},{"issue":"20","key":"22_CR30","doi-asserted-by":"publisher","first-page":"1860","DOI":"10.1016\/j.tcs.2010.12.016","volume":"412","author":"JY Girard","year":"2011","unstructured":"Girard, J.Y.: Geometry of interaction V: Logic in the hyperfinite factor. Theoret. Comput. Sci. 412(20), 1860\u20131883 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"22_CR31","series-title":"Logic, Epistemology, and the Unity of Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-94-007-4435-6_12","volume-title":"Epistemology versus Ontology","author":"JY Girard","year":"2012","unstructured":"Girard, J.Y.: Normativity in logic. In: Dybjer, P., Lindstr\u00f6m, S., Palmgren, E., Sundholm, G. (eds.) Epistemology versus Ontology. LEUS, vol. 27, pp. 243\u2013263. Springer, Heidelberg (2012)"},{"key":"22_CR32","doi-asserted-by":"crossref","first-page":"250","DOI":"10.4204\/EPTCS.129.15","volume":"129","author":"Robert Gl\u00fcck","year":"2013","unstructured":"Gl\u00fcck, R.: Simulation of two-way pushdown automata revisited. In: Banerjee, A., Danvy, O., Doh, K.G., Hatcliff, J. (eds.) Festschrift for Dave Schmidt. EPTCS, vol. 129, pp. 250\u2013258 (2013)","journal-title":"Electronic Proceedings in Theoretical Computer Science"},{"key":"22_CR33","unstructured":"Grellois, C., Melli\u00e9s, P.A.: Relational semantics of linear logic and higher-order model checking. In: Kreutzer, S. (ed.) CSL. LIPIcs, vol. 41, pp. 260\u2013276. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015). \n                      http:\/\/www.dagstuhl.de\/dagpub\/978-3-939897-90-3"},{"key":"22_CR34","unstructured":"Huet, G., Lankford, D.: On the uniform halting problem for term rewriting systems. Research Report RR-283, INRIA (1978). \n                      http:\/\/www.ens-lyon.fr\/LIP\/REWRITING\/TERMINATION\/Huet_Lankford.pdf"},{"issue":"3","key":"22_CR35","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0020-0190(94)90088-4","volume":"49","author":"M Ladermann","year":"1994","unstructured":"Ladermann, M., Petersen, H.: Notes on looping deterministic two-way pushdown automata. Inf. Process. Lett. 49(3), 123\u2013127 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"22_CR36","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.tcs.2003.10.018","volume":"318","author":"Y Lafont","year":"2004","unstructured":"Lafont, Y.: Soft linear logic and polynomial time. Theoret. Comput. Sci. 318(1), 163\u2013180 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"22_CR37","doi-asserted-by":"crossref","unstructured":"Leivant, D.: Stratified functional programs and computational complexity. In: Van Deusen, M.S., Lang, B. (eds.) POPL, pp. 325\u2013333. ACM Press (1993)","DOI":"10.1145\/158511.158659"},{"key":"22_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-540-30477-7_21","volume-title":"Programming Languages and Systems","author":"PM Neergaard","year":"2004","unstructured":"Neergaard, P.M.: A functional language for logarithmic space. In: Chin, W.-N. (ed.) APLAS 2004. LNCS, vol. 3302, pp. 311\u2013326. Springer, Heidelberg (2004)"},{"issue":"1","key":"22_CR39","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/321250.321253","volume":"12","author":"JA Robinson","year":"1965","unstructured":"Robinson, J.A.: A machine-oriented logic based on the resolution principle. J. ACM 12(1), 23\u201341 (1965)","journal-title":"J. ACM"},{"key":"22_CR40","unstructured":"Seiller, T.: Logique dans le facteur hyperfini : g\u00e9ometrie de l\u2019interaction et complexit\u00e9. Ph.D. thesis, Universit\u00e9 de la M\u00e9diterran\u00e9e (2012), \n                      https:\/\/hal.archives-ouvertes.fr\/tel-00768403"},{"key":"22_CR41","unstructured":"Seiller, T.: A correspondence between maximal abelian sub-algebras and linear logic fragments. ArXiv preprint \n                      abs\/1408.2125\n                      \n                    , to appear in MSCS (2014)"},{"key":"22_CR42","unstructured":"Seiller, T.: Interaction graphs: Graphings. ArXiv preprint \n                      abs\/1405.6331\n                      \n                     (2014)"},{"key":"22_CR43","volume-title":"Computational Complexity, Mathematics and its Applications","author":"KW Wagner","year":"1986","unstructured":"Wagner, K.W., Wechsung, G.: Computational Complexity, Mathematics and its Applications. Springer, Heidelberg (1986)"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49630-5_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,23]],"date-time":"2020-03-23T21:07:43Z","timestamp":1584997663000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49630-5_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662496299","9783662496305"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49630-5_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}