References

1. Roland Backhouse, Dexter Kozen & Bernhard Möller (2001): Applications of Kleene Algebra 01081. Dagstuhl-Seminar-Report. Available at https://www.dagstuhl.de/Reports/01/01081.pdf.
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 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.9934.
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 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.401.5051.
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 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.375.1193.
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 http://t2r2.star.titech.ac.jp/rrws/file/CTT100701584/ATD100000413/.
22. Larry Joseph Stockmeyer (1974): The complexity of decision problems in automata theory and logic. Available at https://dspace.mit.edu/handle/1721.1/15540.
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: eptcs@eptcs.org

For website issues: webmaster@eptcs.org