{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T16:25:11Z","timestamp":1790180711379,"version":"4.1.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,2,1]],"date-time":"2009-02-01T00:00:00Z","timestamp":1233446400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2009,2]]},"abstract":"<jats:p>Imposing linearity and ramification constraints allows to weaken higher-order (primitive) recursion in such a way that the class of representable functions equals the class of polynomial-time computable functions, as the works by Leivant, Hofmann, and others show. This article shows that fine-tuning these two constraints leads to different expressive strengths, some of them lying well beyond polynomial time. This is done by introducing a new semantics, called algebraic context semantics. The framework stems from Gonthier's original work (itself a model of Girard's geometry of interaction) and turns out to be a versatile and powerful tool for the quantitative analysis of normalization in the lambda calculus with constants and higher-order recursion.<\/jats:p>","DOI":"10.1145\/1462179.1462180","type":"journal-article","created":{"date-parts":[[2009,2,25]],"date-time":"2009-02-25T14:44:30Z","timestamp":1235573070000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["The geometry of linear higher-order recursion"],"prefix":"10.1145","volume":"10","author":[{"given":"Ugo Dal","family":"Lago","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Bologna, Bologna, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,3,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/647380.724642"},{"key":"e_1_2_1_2_1","first-page":"1","article-title":"Elementary complexity and geometry of interaction","volume":"45","author":"Baillot P.","year":"2001","journal-title":"Fundam. Inf."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01201998"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(00)00006-3"},{"key":"e_1_2_1_5_1","unstructured":"Bonfante G. Marion J.-Y. and Moyen J.-Y. 2004. On complexity analysis by quasi-interpretations. Theor. Comput. Sci. To appear.  Bonfante G. Marion J.-Y. and Moyen J.-Y. 2004. On complexity analysis by quasi-interpretations. Theor. Comput. Sci. To appear."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.21"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780342_11"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24849-1_12"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 11th IEEE Syposium on Logic in Computer Science, 394--405","author":"Danos V."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00049-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040313"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/646125.680751"},{"key":"e_1_2_1_13_1","first-page":"221","article-title":"Geometry of interaction 1: Interpretation of system F","volume":"88","author":"Girard J.-Y.","year":"1989","journal-title":"Proceedings of the Logic Colloquium"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2700"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/143165.143172"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/788021.788962"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(00)00010-5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-002-0156-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.10.018"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158659"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/647849.737072"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(98)00040-2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00078-1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.11.002"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/647844.736567"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/646840.708813"},{"key":"e_1_2_1_27_1","volume-title":"Eds. NATO Science Series","volume":"62","author":"Ostrin G."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Glasgow Workshop on Functional Programming, 298--311","author":"Sands D.","year":"1991"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1122038991"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462179.1462180","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1462179.1462180","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:15Z","timestamp":1750253415000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462179.1462180"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,2]]}},"alternative-id":["10.1145\/1462179.1462180"],"URL":"https:\/\/doi.org\/10.1145\/1462179.1462180","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2]]},"assertion":[{"value":"2006-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}