{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:05Z","timestamp":1753894385475,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T00:00:00Z","timestamp":1645660800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The class of Basic Feasible Functionals BFF$_2$ is the type-2 counterpart of\nthe class FP of type-1 functions computable in polynomial time. Several\ncharacterizations have been suggested in the literature, but none of these\npresent a programming language with a type system guaranteeing this complexity\nbound. We give a characterization of BFF$_2$ based on an imperative language\nwith oracle calls using a tier-based type system whose inference is decidable.\nSuch a characterization should make it possible to link higher-order complexity\nwith programming theory. The low complexity (cubic in the size of the program)\nof the type inference algorithm contrasts with the intractability of the\naforementioned methods and does not overly constrain the expressive power of\nthe language.<\/jats:p>","DOI":"10.46298\/lmcs-18(1:33)2022","type":"journal-article","created":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T17:40:41Z","timestamp":1646329241000},"source":"Crossref","is-referenced-by-count":1,"title":["A tier-based typed programming language characterizing Feasible Functionals"],"prefix":"10.46298","volume":"Volume 18, Issue 1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9750-0460","authenticated-orcid":false,"given":"Emmanuel","family":"Hainry","sequence":"first","affiliation":[]},{"given":"Bruce M.","family":"Kapron","sequence":"additional","affiliation":[]},{"given":"Jean-Yves","family":"Marion","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0601-5425","authenticated-orcid":false,"given":"Romain","family":"P\u00e9choux","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2022,2,24]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/9127\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/9127\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:19:33Z","timestamp":1687292373000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/7216"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,24]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(1:33)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"2102.11605v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2102.11605v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2102.11605v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2102.11605","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2102.11605","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2022,2,24]]},"article-number":"7216"}}