Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Nonelementary problem
open-in-new
<h2 id="references">References</h2> <ol> <li id="fn:1"><p>Vorobyov, Sergei; Voronkov, Andrei (1998), "Complexity of Nonrecursive Logic Programs with Complex Values", Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '98), New York, NY, USA: ACM, pp. 244–253, CiteSeerX 10.1.1.39.8822, doi:10.1145/275487.275515, ISBN 978-0-89791-996-8, S2CID 15631793. <a href="978-0-89791-996-8" target="_blank">978-0-89791-996-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Stockmeyer, Larry J. (1974), The Complexity of Decision Problems in Automata Theory and Logic (PDF), Ph.D. dissertation, Massachusetts Institute of Technology <a href="/wiki/Larry_Stockmeyer" target="_blank">/wiki/Larry_Stockmeyer</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Libkin, Leonid (2006), "Logics for unranked trees: an overview", Logical Methods in Computer Science, 2 (3): 3:2, 31, arXiv:cs.LO/0606062, doi:10.2168/LMCS-2(3:2)2006, MR 2295773. <a href="/wiki/Leonid_Libkin" target="_blank">/wiki/Leonid_Libkin</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Vorobyov, Sergei (1996), "An improved lower bound for the elementary theories of trees", Automated Deduction — CADE-13: 13th International Conference on Automated Deduction New Brunswick, NJ, USA, July 30 – August 3, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1104, Springer, pp. 275–287, CiteSeerX 10.1.1.39.1499, doi:10.1007/3-540-61511-3_91, ISBN 978-3-540-61511-8. <a href="978-3-540-61511-8" target="_blank">978-3-540-61511-8</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Pratt-Hartmann, Ian; Szwast, Wieslaw; Tendera, Lidia (2016), "Quine's fluted fragment is non-elementary", in Talbot, Jean-Marc; Regnier, Laurent (eds.), 25th EACSL Annual Conference on Computer Science Logic, CSL 2016, August 29 - September 1, 2016, Marseille, France, LIPIcs, vol. 62, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 39:1–39:21, doi:10.4230/LIPIcs.CSL.2016.39 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Statman, Richard (1979), "The typed λ-calculus is not elementary recursive", Theoretical Computer Science, 9: 73–81, doi:10.1016/0304-3975(79)90007-0, hdl:2027.42/23535. <a href="/wiki/Richard_Statman" target="_blank">/wiki/Richard_Statman</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Czerwiński, Wojciech; Orlikowski, Łukasz (2021). Reachability in Vector Addition Systems is Ackermann-complete. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). arXiv:2104.13866. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Brubaker, Ben (4 December 2023). "An Easy-Sounding Problem Yields Numbers Too Big for Our Universe". Quanta Magazine. <a href="https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/" target="_blank">https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Leroux, Jerome (February 2022). "The Reachability Problem for Petri Nets is Not Primitive Recursive". 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 1241–1252. arXiv:2104.12695. doi:10.1109/FOCS52979.2021.00121. ISBN 978-1-6654-2055-6. <a href="978-1-6654-2055-6" target="_blank">978-1-6654-2055-6</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Brubaker, Ben (4 December 2023). "An Easy-Sounding Problem Yields Numbers Too Big for Our Universe". Quanta Magazine. <a href="https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/" target="_blank">https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> </ol>