{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T07:53:45Z","timestamp":1781855625123,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":28,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,7,9]],"date-time":"2018-07-09T00:00:00Z","timestamp":1531094400000},"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":[[2018,7,9]]},"DOI":"10.1145\/3209108.3209124","type":"proceedings-article","created":{"date-parts":[[2018,6,27]],"date-time":"2018-06-27T08:14:43Z","timestamp":1530087283000},"page":"579-588","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Type-two polynomial-time and restricted lookahead"],"prefix":"10.1145","author":[{"given":"Bruce M.","family":"Kapron","sequence":"first","affiliation":[{"name":"University of Victoria, Victoria, BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florian","family":"Steinberg","sequence":"additional","affiliation":[{"name":"INRIA, Sophia-Antipolis, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1575"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90034-7"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/507382.507387"},{"key":"e_1_3_2_1_4_1","volume-title":"Methodology and Philosophy of Science: Proc. 1964 Intl. Congress (Studies in Logic and the Foundations of Mathematics), Yehoshua Bar-Hillel (Ed.). North-Holland Publishing, 24--30","author":"Cobham A.","year":"1965","unstructured":"A. Cobham. 1965. The intrinsic computational difficulty of functions. In Logic, Methodology and Philosophy of Science: Proc. 1964 Intl. Congress (Studies in Logic and the Foundations of Mathematics), Yehoshua Bar-Hillel (Ed.). North-Holland Publishing, 24--30."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804041"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_3_2_1_7_1","volume-title":"Logic from computer science (Berkeley","author":"Cook S.A.","year":"1989","unstructured":"S.A. Cook. 1992. Computability and complexity of higher type functions. In Logic from computer science (Berkeley, CA, 1989). Math. Sci. Res. Inst. Publ., Vol. 21. Springer, New York, 51--72."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"S.A. Cook and B.M. Kapron. 1990. Characterizations of the basic feasible functionals of finite type. In Feasible mathematics (Ithaca NY 1989). Birkh\u00e4user 71--96.","DOI":"10.1007\/978-1-4612-3466-1_5"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90044-E"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"N. Danner and J.S. Royer. 2007. Adventures in time and space. Log. Methods Comput. Sci. 3 1 (2007) 1:9 53.","DOI":"10.2168\/LMCS-3(1:9)2007"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.02.003"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/976706.976713"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800003841"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794263452"},{"key":"e_1_3_2_1_15_1","unstructured":"B.M. Kapron and F. Steinberg. 2018. Type-two polynomial-time and restricted lookahead. preprint. (2018). https:\/\/arxiv.org\/abs\/1801.07485"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","unstructured":"A. Kawamura and S.A. Cook. 2012. Complexity Theory for Operators in Analysis. TOCT 4 2 (2012) 5:1--5:24. 10.1145\/2189778.2189780","DOI":"10.1145\/2189778.2189780"},{"key":"e_1_3_2_1_17_1","volume-title":"Part II. LNCS","volume":"8635","author":"Kawamura A.","unstructured":"A. Kawamura and H. Ota. 2014. Small complexity classes for computable analysis. In Mathematical foundations of computer science 2014. Part II. LNCS, Vol. 8635. Springer, Heidelberg, 432--444."},{"key":"e_1_3_2_1_18_1","volume-title":"2nd International Conference on Formal Structures for Computation and Deduction","author":"Kawamura A.","year":"2017","unstructured":"A. Kawamura and F. Steinberg. 2017. Polynomial running times for polynomial-time oracle machines. In 2nd International Conference on Formal Structures for Computation and Deduction, 2017, Oxford, UK. 23:1--23:18."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/647852.760817"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80035-9"},{"key":"e_1_3_2_1_21_1","volume-title":"Computational complexity","author":"Papadimitriou C.H.","unstructured":"C.H. Papadimitriou. 1994. Computational complexity. Addison-Wesley Publishing Company, Reading, MA. xvi+523 pages."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/647847.736892"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1487"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.10.024"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1992.185541"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1993.287576"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.009"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093635419"}],"event":{"name":"LICS '18: 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Oxford United Kingdom","acronym":"LICS '18","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","IEEE-CS\\DATC IEEE Computer Society","EACSL European Association for Computer Science Logic"]},"container-title":["Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209108.3209124","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209108.3209124","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T07:31:12Z","timestamp":1781854272000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209108.3209124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,9]]},"references-count":28,"alternative-id":["10.1145\/3209108.3209124","10.1145\/3209108"],"URL":"https:\/\/doi.org\/10.1145\/3209108.3209124","relation":{},"subject":[],"published":{"date-parts":[[2018,7,9]]},"assertion":[{"value":"2018-07-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}