{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T14:54:08Z","timestamp":1791125648684,"version":"4.1.0"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2012,2,2]],"date-time":"2012-02-02T00:00:00Z","timestamp":1328140800000},"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":[[2012,8]]},"abstract":"<jats:p>Quasi-interpretations are a technique for guaranteeing complexity bounds on first-order functional programs: in particular, with termination orderings, they give a sufficient condition for a program to be executable in polynomial time (Marion and Moyen 2000), which we call the P-criterion here. We study properties of the programs satisfying the P-criterion in order to improve the understanding of its intensional expressive power. Given a program, its blind abstraction is the non-deterministic program obtained by replacing all constructors with the same arity by a single one. A program is blindly polytime if its blind abstraction terminates in polynomial time. We show that all programs satisfying a variant of the P-criterion are in fact blindly polytime. Then we give two extensions of the P-criterion: one relaxing the termination ordering condition and the other (the bounded-value property) giving a necessary and sufficient condition for a program to be polynomial time executable, with memoisation.<\/jats:p>","DOI":"10.1017\/s0960129511000685","type":"journal-article","created":{"date-parts":[[2012,2,2]],"date-time":"2012-02-02T09:05:19Z","timestamp":1328173519000},"page":"549-580","source":"Crossref","is-referenced-by-count":5,"title":["On quasi-interpretations, blind abstractions and implicit complexity"],"prefix":"10.1017","volume":"22","author":[{"given":"PATRICK","family":"BAILLOT","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"UGO","family":"DAL LAGO","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"JEAN-YVES","family":"MOYEN","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2012,2,2]]},"reference":[{"key":"S0960129511000685_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322230"},{"key":"S0960129511000685_ref25","unstructured":"P\u00e9choux R. (2007) Analyse de la complexit\u00e9 des programmes par interpr\u00e9tation s\u00e9mantique, Ph.D. Thesis, Institut National Polytechnique de Lorraine."},{"key":"S0960129511000685_ref9","unstructured":"Dal Lago U. (2007) Note on the intentional expressive power of bounded calculi. Manuscript available at http:\/\/www.cs.unibo.it\/~dallago\/iepbc.pdf."},{"key":"S0960129511000685_ref23","doi-asserted-by":"publisher","DOI":"10.1145\/1555746.1555751"},{"key":"S0960129511000685_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.02.007"},{"key":"S0960129511000685_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75292-9_28"},{"key":"S0960129511000685_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90026-3"},{"key":"S0960129511000685_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00009-9"},{"key":"S0960129511000685_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/11737414_12"},{"key":"S0960129511000685_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45575-2_46"},{"key":"S0960129511000685_ref1","first-page":"29","article-title":"Synthesis of max-plus quasi-interpretations","volume":"65","author":"Amadio","year":"2005","journal-title":"Fundamenta Informaticae"},{"key":"S0960129511000685_ref12","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1999.782641"},{"key":"S0960129511000685_ref18","first-page":"320","volume-title":"Feasible Mathematics II","author":"Leivant","year":"1994"},{"key":"S0960129511000685_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00011-7"},{"key":"S0960129511000685_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800003877"},{"key":"S0960129511000685_ref16","unstructured":"Kamin S. and L\u00e9vy J.-J. (1980) Attempts for generalising the recursive path orderings. Technical report, University of Illinois, Urbana Champaign. Available at http:\/\/perso.ens-lyon.fr\/pierre.lescanne\/not_accessible.html#termination."},{"key":"S0960129511000685_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78969-7_11"},{"key":"S0960129511000685_ref6","doi-asserted-by":"crossref","unstructured":"Bonfante G. , Marion J.-Y. and Moyen J.-Y. (2005) Quasi-Interpretations and Small Space Bounds. In: Proceedings of The International Conference on Rewriting Techniques and Applications (RTA 2005). Springer-Verlag Lecture Notes in Computer Science 3467.","DOI":"10.1007\/978-3-540-32033-3_12"},{"key":"S0960129511000685_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00357-0"},{"key":"S0960129511000685_ref17","volume-title":"Term Rewriting Systems","author":"Klop","year":"2003"},{"key":"S0960129511000685_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0037112"},{"key":"S0960129511000685_ref21","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/3-540-44404-1_3","article-title":"Efficient First Order Functional Program Interpreter with Time Bound Certifications. In: Proceedings of Logic for Programming Artificial Intelligence and Reasoning (LPAR '00)","volume":"1955","author":"Marion","year":"2000","journal-title":"Springer-Verlag Lecture Notes in Artificial Intelligence"},{"key":"S0960129511000685_ref24","unstructured":"Moyen J.-Y. (2003) Analyse de la complexit\u00e9 et transformation de programmes, Th\u00e8se d'Universit\u00e9 (Ph.D. Thesis), University Nancy 2."},{"key":"S0960129511000685_ref11","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2700"},{"key":"S0960129511000685_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01201998"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129511000685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T15:01:09Z","timestamp":1556204469000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129511000685\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,2]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["S0960129511000685"],"URL":"https:\/\/doi.org\/10.1017\/s0960129511000685","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,2]]}}}