References

  1. M. Agrawal, N. Kayal & N. Saxena (2004): PRIMES is in P.. Annals of mathematics, pp. 781–793. Available at http://dx.doi.org/10.4007/annals.2004.160.781.
  2. J. Amilhastre, P. Janssen & M-C. Vilarem (2001): FA Minimisation Heuristics for a Class of Finite Languages. Lecture Notes in Computer Science 2214, pp. 1 – 12. Available at http://dx.doi.org/10.1007/3-540-45526-4_1.
  3. J.-C. Birget (1992): Intersection and union of regular languages and state complexity. Information Processing Letters 43, pp. 185–190. Available at http://dx.doi.org/10.1016/0020-0190(92)90198-5.
  4. C. Câmpeanu, A. Paun & S. Yu (2002): An Efficient Algorithm for Constructing Minimal Cover Automata for Finite Languages. International Journal of Foundations of Computer Science 13(1), pp. 83 – 97. Available at http://dx.doi.org/10.1142/S0129054102000960.
  5. C. Câmpeanu, K. Culik II, K. Salomaa & S. Yu (2001): State complexity of basic operations on finite languages. Lecture Notes in Computer Science 2214, pp. 60–70. Available at http://dx.doi.org/10.1007/3-540-45526-4_6.
  6. C. Câmpeanu, N. Santean & S. Yu (1986): Minimal cover-automata for finite languages. Theoretical Computer Science 267(1-2), pp. 3–16. Available at http://dx.doi.org/10.1016/S0304-3975(00)00292-9.
  7. M. Chrobak (1986): Finite Automata and Unary Languages. Theoretical Computer Science 47(2), pp. 149–158. Available at http://dx.doi.org/10.1016/0304-3975(86)90142-8.
  8. G.Gramlich (2003): Probabilistic and Nondeterministic Unary Automata. Lecture Notes in Computer Science 2747, pp. 460 – 469. Available at http://dx.doi.org/10.1007/978-3-540-45138-9_40.
  9. I. Glaister & J. Shallit (1996): A lower bound technique for the size of nondeterministic finite automata. Information Processing Letters 59, pp. 75 – 77. Available at http://dx.doi.org/10.1016/0020-0190(96)00095-6.
  10. H. Gruber & M. Holzer (2006): Finding lower bounds for nondeterministic state complexity is hard. Lecture Notes in Computer Science 4036, pp. 363–374. Available at http://dx.doi.org/10.1007/11779148_33.
  11. H. Gruber & M. Holzer (2007): Computational Complexity of NFA Minimization for Finite and Unary Languages. LATA 8, pp. 261–272. Available at http://www2.tcs.ifi.lmu.de/~gruberh/data/lata07-submission.pdf.
  12. M. Holzer & M. Kutrib (2003): State complexity of basic operations on nondeterministic finite automata. Lecture Notes in Computer Science 2608, pp. 148–157. Available at http://dx.doi.org/10.1007/3-540-44977-9_14.
  13. M. Holzer & M. Kutrib (2003): Unary language operations and their nondeterministic state complexity. Lecture Notes in Computer Science 2450, pp. 162–172. Available at http://dx.doi.org/10.1007/3-540-45005-X_14.
  14. M. Holzer & M. Kutrib (2009): Descriptional and computational complexity of finite automata. Lecture Notes in Computer Science 5457, pp. 23–42. Available at http://dx.doi.org/10.1007/978-3-642-00982-2_3.
  15. M. Holzer & M. Kutrib (2009): Nondeterministic finite automata - recent results on the descriptional and computational complexity. Int. J. Found. Comput. Sci 20(4), pp. 563–580. Available at http://dx.doi.org/10.1142/S0129054109006747.
  16. John Hopcroft (1971): An n logn Algorithm for Minimizing States in a Finite Automaton. In: Z. Kohavi & A. Paz: Theory of Machines and Computations. Academic Press, New York, pp. 189–196.
  17. John E. Hopcroft & Jeffrey D. Ullman (1979): Introduction to Automata Theory, Languages and Computation. Addison-Wesley.
  18. L. Ilie, G. Navarro & S. Yu (2004): On NFA reductions. Lecture Notes in Computer Science Volume: Theory Is Forever Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday 3113, pp. 112–124. Available at http://dx.doi.org/10.1007/978-3-540-27812-2_11.
  19. T. Jiang & B. Ravikumar (1993): NFA minimization problems are hard. SIAM Journal on Computing 22(1), pp. 117–141.
  20. N. Koblitz (1994): A Course in Number Theory and Criptography. Springer. Available at http://dx.doi.org/10.1007/978-1-4419-8592-7.
  21. H. Körner (2003): A Time and Space Efficient Algorithm for Minimizing Cover Automata for Finite Languages. International Journal of Foundations of Computer Science 14(6), pp. 1071–1086. Available at http://dx.doi.org/10.1142/S0129054103002187.
  22. A. N. Maslov (1970): Estimates of the number of states of finite automata. Soviet Mathematics Doklady 11, pp. 1373–1374.
  23. A. N. Maslov (1973): Cyclic shift operation for languages. Probl. Inf. Transm 9, pp. 333–338.
  24. F. Mera & G. Pighizzini (2005): Complementing unary nondeterministic automata. Theoretical Computer Science 330, pp. 349–360. Available at http://dx.doi.org/10.1016/j.tcs.2004.04.015.
  25. E. F. Moore (1956): Gedanken-experiments on sequential machines. Automata studies, Annals of mathematics studies 34, pp. 129–153.
  26. D. Revuz (1992): Minimisation of acyclic deterministic automata in linear time. Theoretical Computer Science 92(1), pp. 181 – 189. Available at http://dx.doi.org/10.1147/rd.32.0114.
  27. S. Yu, K. Salomaa & Q. Zhuang (1994): The state complexities of some basic operations on regular languages. Theoretical Computer Science 125(2), pp. 315–328. Available at http://dx.doi.org/10.1016/0304-3975(92)00011-F.
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org