{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T23:28:59Z","timestamp":1759879739279,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T00:00:00Z","timestamp":1594166400000},"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":[],"published-print":{"date-parts":[[2020,7,8]]},"DOI":"10.1145\/3373718.3394768","type":"proceedings-article","created":{"date-parts":[[2020,5,26]],"date-time":"2020-05-26T00:23:18Z","timestamp":1590452598000},"page":"535-549","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A tier-based typed programming language characterizing Feasible Functionals"],"prefix":"10.1145","author":[{"given":"Emmanuel","family":"Hainry","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, Inria, LORIA, Nancy, France"}]},{"given":"Bruce M.","family":"Kapron","sequence":"additional","affiliation":[{"name":"University of Victoria, Canada"}]},{"given":"Jean-Yves","family":"Marion","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, LORIA, Nancy, France"}]},{"given":"Romain","family":"P\u00e9choux","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, Inria, LORIA, Nancy, France"}]}],"member":"320","published-online":{"date-parts":[[2020,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90002-4"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2015.12.008"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.09.015"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2004.1319621"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01201998"},{"volume-title":"Polynomial or Exponential? Complexity Inference in Polynomial Time. In Logic and Theory of Algorithms","author":"Ben-Amram Amir M.","key":"e_1_3_2_1_6_1","unstructured":"Amir M. Ben-Amram , Neil D. Jones , and Lars Kristiansen . 2008. Linear , Polynomial or Exponential? Complexity Inference in Polynomial Time. In Logic and Theory of Algorithms . Springer , 67--76. Amir M. Ben-Amram, Neil D. Jones, and Lars Kristiansen. 2008. Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time. In Logic and Theory of Algorithms. Springer, 67--76."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.02.007"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science, Y. Bar-Hillel (Ed.). North-Holland","author":"Cobham Alan","year":"1965","unstructured":"Alan Cobham . 1965 . The intrinsic computational difficulty of functions . In Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science, Y. Bar-Hillel (Ed.). North-Holland , Amsterdam, 24--30. Alan Cobham. 1965. The intrinsic computational difficulty of functions. In Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science, Y. Bar-Hillel (Ed.). North-Holland, Amsterdam, 24--30."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804041"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11817963_37"},{"volume-title":"Logic from Computer Science","author":"Cook Stephen A","key":"e_1_3_2_1_11_1","unstructured":"Stephen A Cook . 1992. Computability and complexity of higher type functions . In Logic from Computer Science . Springer , 51--72. https: \/\/doi.org\/10.1007\/978-1-4612-2822-6_3 10.1007\/978-1-4612-2822-6_3 Stephen A Cook. 1992. Computability and complexity of higher type functions. In Logic from Computer Science. Springer, 51--72. https: \/\/doi.org\/10.1007\/978-1-4612-2822-6_3"},{"key":"e_1_3_2_1_12_1","volume-title":"30th Annual Symposium on Foundations of Computer Science (FOCS 1989","author":"Stephen","year":"1989","unstructured":"Stephen A. Cook and Bruce M. Kapron. 1989. Characterizations of the basic feasible functionals of finite type . In 30th Annual Symposium on Foundations of Computer Science (FOCS 1989 ). IEEE, 154--159. https: \/\/doi.org\/10.1109\/SFCS. 1989 .63471 10.1109\/SFCS.1989.63471 Stephen A. Cook and Bruce M. Kapron. 1989. Characterizations of the basic feasible functionals of finite type. In 30th Annual Symposium on Foundations of Computer Science (FOCS 1989). IEEE, 154--159. https: \/\/doi.org\/10.1109\/SFCS.1989.63471"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90044-E"},{"volume-title":"Proceedings of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2006. ACM, 168--179","author":"Danner Norman","key":"e_1_3_2_1_14_1","unstructured":"Norman Danner and James S. Royer . 2006. Adventures in time and space . In Proceedings of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2006. ACM, 168--179 . https:\/\/doi.org\/10.1145\/1111037.1111053 10.1145\/1111037.1111053 Norman Danner and James S. Royer. 2006. Adventures in time and space. In Proceedings of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2006. ACM, 168--179. https:\/\/doi.org\/10.1145\/1111037.1111053"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205048"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.03.008"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328456"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2700"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37075-5_20"},{"key":"e_1_3_2_1_20_1","volume-title":"APLAS 2015 (Lecture Notes in Computer Science). Springer, 387--404","author":"Hainry Emmanuel","year":"2015","unstructured":"Emmanuel Hainry and Romain P\u00e9choux . 2015 . Objects in Polynomial Time. In Programming Languages and Systems - 13th Asian Symposium , APLAS 2015 (Lecture Notes in Computer Science). Springer, 387--404 . https: \/\/doi.org\/10.1007\/978-3-319-26529-2_21 10.1007\/978-3-319-26529-2_21 Emmanuel Hainry and Romain P\u00e9choux. 2015. Objects in Polynomial Time. In Programming Languages and Systems - 13th Asian Symposium, APLAS 2015 (Lecture Notes in Computer Science). Springer, 387--404. https: \/\/doi.org\/10.1007\/978-3-319-26529-2_21"},{"key":"e_1_3_2_1_21_1","volume-title":"21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning. EasyChair, 269--285","author":"Hainry Emmanuel","year":"2017","unstructured":"Emmanuel Hainry and Romain P\u00e9choux . 2017 . Higher order interpretation for higher order complexity. In LPAR-21 , 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning. EasyChair, 269--285 . https:\/\/doi.org\/10.29007\/1tkw 10.29007\/1tkw Emmanuel Hainry and Romain P\u00e9choux. 2017. Higher order interpretation for higher order complexity. In LPAR-21, 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning. EasyChair, 269--285. https:\/\/doi.org\/10.29007\/1tkw"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90046-X"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800003841"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555746.1555752"},{"key":"e_1_3_2_1_25_1","volume-title":"32nd Annual Symposium on Foundations of Computer Science","author":"Bruce","year":"1991","unstructured":"Bruce M. Kapron and Stephen A. Cook. 1991. A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract) . In 32nd Annual Symposium on Foundations of Computer Science , San Juan, Puerto Rico , 1-4 October 1991 . IEEE, 342--347. https:\/\/doi.org\/10.1109\/SFCS.1991.185389 10.1109\/SFCS.1991.185389 Bruce M. Kapron and Stephen A. Cook. 1991. A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract). In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991. IEEE, 342--347. https:\/\/doi.org\/10.1109\/SFCS.1991.185389"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794263452"},{"key":"e_1_3_2_1_27_1","volume-title":"LICS 2018","author":"Bruce","year":"2091","unstructured":"Bruce M. Kapron and Florian Steinberg. 2018. Type-two polynomial-time and restricted lookahead. In Logic in Computer Science , LICS 2018 . ACM, 579--588. https:\/\/doi.org\/10.1145\/3 2091 08.3209124 10.1145\/3209108.3209124 Bruce M. Kapron and Florian Steinberg. 2018. Type-two polynomial-time and restricted lookahead. In Logic in Computer Science, LICS 2018. ACM, 579--588. https:\/\/doi.org\/10.1145\/3209108.3209124"},{"volume-title":"Proceedings Third Joint Workshop on Developments in Implicit Computational complExity and Foundational & Practical Aspects of Resource Analysis, DICE-FOPARA@ETAPS 2019 (EPTCS). 61--73","author":"Bruce","key":"e_1_3_2_1_28_1","unstructured":"Bruce M. Kapron and Florian Steinberg. 2019. Type-two iteration with bounded query revision . In Proceedings Third Joint Workshop on Developments in Implicit Computational complExity and Foundational & Practical Aspects of Resource Analysis, DICE-FOPARA@ETAPS 2019 (EPTCS). 61--73 . https:\/\/doi.org\/10.4204\/EPTCS.298.5 10.4204\/EPTCS.298.5 Bruce M. Kapron and Florian Steinberg. 2019. Type-two iteration with bounded query revision. In Proceedings Third Joint Workshop on Developments in Implicit Computational complExity and Foundational & Practical Aspects of Resource Analysis, DICE-FOPARA@ETAPS 2019 (EPTCS). 61--73. https:\/\/doi.org\/10.4204\/EPTCS.298.5"},{"key":"e_1_3_2_1_29_1","volume-title":"Polynomial Running Times for Polynomial-Time Oracle Machines. In 2nd International Conference on Formal Structures for Computation and Deduction, FSCD 2017","author":"Kawamura Akitoshi","year":"2017","unstructured":"Akitoshi Kawamura and Florian Steinberg . 2017 . Polynomial Running Times for Polynomial-Time Oracle Machines. In 2nd International Conference on Formal Structures for Computation and Deduction, FSCD 2017 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 23:1--23:18. https:\/\/doi.org\/10.4230\/LIPIcs.FSCD. 2017.23 10.4230\/LIPIcs.FSCD.2017.23 Akitoshi Kawamura and Florian Steinberg. 2017. Polynomial Running Times for Polynomial-Time Oracle Machines. In 2nd International Conference on Formal Structures for Computation and Deduction, FSCD 2017. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 23:1--23:18. https:\/\/doi.org\/10.4230\/LIPIcs.FSCD.2017.23"},{"volume-title":"Conference Record of POPL 2001: The 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, 81--92","author":"Lee Chin Soon","key":"e_1_3_2_1_30_1","unstructured":"Chin Soon Lee , Neil D. Jones , and Amir M . Ben-Amram. 2001. The size-change principle for program termination . In Conference Record of POPL 2001: The 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, 81--92 . https:\/\/doi.org\/10.1145\/360204.360210 10.1145\/360204.360210 Chin Soon Lee, Neil D. Jones, and Amir M. Ben-Amram. 2001. The size-change principle for program termination. In Conference Record of POPL 2001: The 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, 81--92. https:\/\/doi.org\/10.1145\/360204.360210"},{"volume-title":"Ramified recurrence and computational complexity I: Word recurrence and poly-time","author":"Leivant Daniel","key":"e_1_3_2_1_31_1","unstructured":"Daniel Leivant . 1995. Ramified recurrence and computational complexity I: Word recurrence and poly-time . In Feasible Mathematics II, Peter Clote and Jeffrey B. Remmel (Eds.). Birkh\u00e4user , Boston, MA , 320--343. https:\/\/doi.org\/10.1007\/978-1-4612-2566-9_11 10.1007\/978-1-4612-2566-9_11 Daniel Leivant. 1995. Ramified recurrence and computational complexity I: Word recurrence and poly-time. In Feasible Mathematics II, Peter Clote and Jeffrey B. Remmel (Eds.). Birkh\u00e4user, Boston, MA, 320--343. https:\/\/doi.org\/10.1007\/978-1-4612-2566-9_11"},{"key":"e_1_3_2_1_32_1","volume-title":"40th International Colloquium, ICALP 2013, Proceedings, Part II (Lecture Notes in Computer Science). Springer, 349--360","author":"Leivant Daniel","year":"2013","unstructured":"Daniel Leivant and Jean-Yves Marion . 2013 . Evolving Graph-Structures and Their Implicit Computational Complexity. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings, Part II (Lecture Notes in Computer Science). Springer, 349--360 . https: \/\/doi.org\/10.1007\/978-3-642-39212-2_32 10.1007\/978-3-642-39212-2_32 Daniel Leivant and Jean-Yves Marion. 2013. Evolving Graph-Structures and Their Implicit Computational Complexity. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings, Part II (Lecture Notes in Computer Science). Springer, 349--360. https: \/\/doi.org\/10.1007\/978-3-642-39212-2_32"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/175469.175474"},{"key":"e_1_3_2_1_34_1","volume-title":"LICS 2011","author":"Marion Jean-Yves","year":"2011","unstructured":"Jean-Yves Marion . 2011 . A Type System for Complexity Flow Analysis. In Logic in Computer Science , LICS 2011 . IEEE Computer Society, 123--132. https:\/\/doi.org\/10.1109\/LICS. 2011.41 10.1109\/LICS.2011.41 Jean-Yves Marion. 2011. A Type System for Complexity Flow Analysis. In Logic in Computer Science, LICS 2011. IEEE Computer Society, 123--132. https:\/\/doi.org\/10.1109\/LICS.2011.41"},{"key":"e_1_3_2_1_35_1","volume-title":"TAMC 2014 (Lecture Notes in Computer Science). Springer, 124--140","author":"Marion Jean-Yves","year":"2014","unstructured":"Jean-Yves Marion and Romain P\u00e9choux . 2014 . Complexity Information Flow in a Multi-threaded Imperative Language. In Theory and Applications of Models of Computation , TAMC 2014 (Lecture Notes in Computer Science). Springer, 124--140 . https:\/\/doi.org\/10.1007\/978-3-319-06089-7_9 10.1007\/978-3-319-06089-7_9 Jean-Yves Marion and Romain P\u00e9choux. 2014. Complexity Information Flow in a Multi-threaded Imperative Language. In Theory and Applications of Models of Computation, TAMC 2014 (Lecture Notes in Computer Science). Springer, 124--140. https:\/\/doi.org\/10.1007\/978-3-319-06089-7_9"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80035-9"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000113"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/353629.353648"}],"event":{"name":"LICS '20: 35th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society"],"location":"Saarbr\u00fccken Germany","acronym":"LICS '20"},"container-title":["Proceedings of the 35th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394768","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3373718.3394768","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:35Z","timestamp":1750197755000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394768"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,8]]},"references-count":38,"alternative-id":["10.1145\/3373718.3394768","10.1145\/3373718"],"URL":"https:\/\/doi.org\/10.1145\/3373718.3394768","relation":{},"subject":[],"published":{"date-parts":[[2020,7,8]]},"assertion":[{"value":"2020-07-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}