References

  1. Siddharth Bhaskar & Jakob G. Simonsen (2020): Implicit Complexity via Controlled Construction and Destruction. Technical Report. Department of Computer Science, University of Copenhagen.
  2. Guillaume Bonfante (2006): Some Programming Languages for Logspace and Ptime. In: Michael Johnson & Varmo Vene: Algebraic Methodology and Software Technology, 11th International Conference, AMAST 2006, Kuressaare, Estonia, July 5-8, 2006, Proceedings, Lecture Notes in Computer Science 4019. Springer, pp. 66–80, doi:10.1007/11784180_8.
  3. Stephen A. Cook (1971): Characterizations of Pushdown Machines in Terms of Time-Bounded Computers. J. ACM 18(1), pp. 4–18, doi:10.1145/321623.321625.
  4. Sheila A. Greibach (1975): Theory of Program Structures: Schemes, Semantics, Verification. Lecture Notes in Computer Science 36. Springer, doi:10.1007/BFb0023017.
  5. Neil Immerman (1988): Nondeterministic Space is Closed Under Complementation. SIAM J. Comput. 17(5), pp. 935–938, doi:10.1137/0217058.
  6. Neil D. Jones (1997): Computability and complexity - from a programming perspective. Foundations of computing series. MIT Press, doi:10.7551/mitpress/2003.001.0001.
  7. Neil D. Jones (1999): LOGSPACE and PTIME Characterized by Programming Languages. Theor. Comput. Sci. 228(1-2), pp. 151–174, doi:10.1016/S0304-3975(98)00357-0.
  8. Neil D. Jones (2001): The expressive power of higher-order types or, life without CONS. J. Funct. Program. 11(1), pp. 55–94, doi:10.1017/S0956796800003889. Available at http://journals.cambridge.org/action/displayAbstract?aid=68581.
  9. Donald E. Knuth (1973): The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley.
  10. Cynthia Kop & Jakob Grue Simonsen (2017): The Power of Non-determinism in Higher-Order Implicit Complexity - Characterising Complexity Classes Using Non-deterministic Cons-Free Programming. In: Hongseok Yang: Programming Languages and Systems - 26th European Symposium on Programming, ESOP 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings, Lecture Notes in Computer Science 10201. Springer, pp. 668–695, doi:10.1007/978-3-662-54434-1_25.
  11. Sige-Yuki Kuroda (1964): Classes of languages and linear-bounded automata. Information and Control 7(2), pp. 207–223, doi:10.1016/S0019-9958(64)90120-2.
  12. John McCarthy (1960): Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Commun. ACM 3(4), pp. 184–195, doi:10.1145/367177.367199.
  13. Yiannis Moschovakis (2019): Abstract Recursion and Intrinsic Complexity. Cambridge University Press (Lecture Notes in Logic), doi:10.1017/9781108234238.
  14. Christos H. Papadimitriou (1994): Computational complexity. Addison-Wesley.
  15. Walter J. Savitch (1970): Relationships Between Nondeterministic and Deterministic Tape Complexities. J. Comput. Syst. Sci. 4(2), pp. 177–192, doi:10.1016/S0022-0000(70)80006-X.
  16. Róbert Szelepcsényi (1988): The Method of Forced Enumeration for Nondeterministic Automata. Acta Inf. 26(3), pp. 279–284, doi:10.1007/BF00299636.
  17. Alan M. Turing (1936-7): On Computable Numbers with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 42(2), pp. 230–265, doi:10.1112/plms/s2-42.1.230.

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org