1. Roland Backhouse, Dexter Kozen & Bernhard Möller (2001): Applications of Kleene Algebra 01081. Dagstuhl-Seminar-Report. Available at
  2. Andrew Badr (2008): Hyper-Minimization in O(n^2). In: Proceedings of the 13th International Conference on Implementation and Applications of Automata, CIAA '08. Springer-Verlag, Berlin, Heidelberg, pp. 223–231, doi:10.1007/978-3-540-70844-5_23.
  3. Andrew Badr, Viliam Geffert & Ian Shipman (2009): Hyper-minimizing minimized deterministic finite state automata. RAIRO - Theoretical Informatics and Applications 43, pp. 69–94, doi:10.1051/ita:2007061.
  4. Jean Berstel (1973): Sur la densité asymptotique de langages formels. In: International Colloquium on Automata, Languages and Programming (ICALP, 1972). North-Holland, pp. 345–358.
  5. Jean Berstel, Dominique Perrin & Christophe Reutenauer (2010): Codes and automata 129. Cambridge University Press. Available at
  6. J Richard Büchi (1960): Weak Second-Order Arithmetic and Finite Automata. Mathematical Logic Quarterly 6(1-6), pp. 66–92, doi:10.1002/malq.19600060105.
  7. Stephen A Cook (1971): The complexity of theorem-proving procedures. In: Proceedings of the third annual ACM symposium on Theory of computing. ACM, pp. 151–158, doi:10.1145/800157.805047.
  8. Markus Holzer & Sebastian Jakobi (2012): From Equivalence to Almost-Equivalence, and Beyond - Minimizing Automata with Errors - (Extended Abstract). In: Developments in Language Theory - 16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012. Proceedings, pp. 190–201, doi:10.1007/978-3-642-31653-1_18.
  9. Harry B Hunt, Daniel J Rosenkrantz & Thomas G Szymanski (1976): On the equivalence, containment, and covering problems for the regular and context-free languages. Journal of Computer and System Sciences 12(2), pp. 222–268, doi:10.1016/S0022-0000(76)80038-4.
  10. Neil Immerman (1988): Nondeterministic space is closed under complementation. SIAM Journal on computing 17(5), pp. 935–938, doi:10.1137/0217058.
  11. Neil Immerman (2012): Descriptive complexity. Springer Science & Business Media, doi:10.1007/978-1-4612-0539-5.
  12. Neil D Jones (1975): Space-bounded reducibility among combinatorial problems. Journal of Computer and System Sciences 11(1), pp. 68–85, doi:10.1016/S0022-0000(75)80050-X.
  13. Leonid Libkin (2004): Elements of finite model theory. Springer Science & Business Media, doi:10.1007/978-3-662-07003-1.
  14. James F Lynch (1993): Convergence laws for random words. Australasian Journal of Combinatorics 7, pp. 145–156. Available at
  15. AR Meyer & LJ Stockmeyer (1973): Word problems requiring exponential time. In: Proc. STOC 73, pp. 1–9, doi:10.1145/800125.804029.
  16. M. Muresan (2009): A Concrete Approach to Classical Analysis. CMS Books in Mathematics. Springer New York, doi:10.1007/978-0-387-78933-0.
  17. Jean-Éric Pin (2010): Mathematical foundations of automata theory. Lecture notes LIAFA, Université Paris 7. Available at
  18. Jacques Sakarovitch (2009): Elements of automata theory. Cambridge University Press, doi:10.1017/CBO9781139195218.
  19. Arto Salomaa & Matti Soittola (1978): Automata-theoretic aspects of formal power series. Springer Science & Business Media, doi:10.1007/978-1-4612-6264-0.
  20. Ryoma Sin'ya (2015): An Automata Theoretic Approach to the Zero-One Law for Regular Languages: Algorithmic and Logical Aspects. In: Proceedings Sixth International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2015, Genoa, Italy, 21-22nd September 2015., pp. 172–185, doi:10.4204/EPTCS.193.13.
  21. Ryoma Sin'ya (2016): Zero-One Law for Regular Languages. Ph.D. Thesis. Tokyo Insutitute of Technology, Japan. Available at
  22. Larry Joseph Stockmeyer (1974): The complexity of decision problems in automata theory and logic. Available at
  23. Róbert Szelepcsényi (1988): The method of forced enumeration for nondeterministic automata. Acta Informatica 26(3), pp. 279–284, doi:10.1007/BF00299636.
  24. Andrew Szilard, Sheng Yu, Kaizhong Zhang & Jeffrey Shallit (1992): Characterizing regular languages with polynomial densities. In: International Symposium on Mathematical Foundations of Computer Science. Springer, pp. 494–503, doi:10.1007/3-540-55808-X_48.
  25. Ken Thompson (1968): Programming Techniques: Regular Expression Search Algorithm. Commun. ACM 11(6), pp. 419–422, doi:10.1145/363347.363387.
  26. Boris A Trakhtenbrot (1950): Impossibility of an algorithm for the decision problem on finite classes (in Russian). Doklady Akademii Nauk SSSR 70, pp. 569–572.

Comments and questions to:
For website issues: