1. M. Adler & N. Immerman (2003): An n! lower bound on formula size. ACM Trans. Comput. Log. 4(3), pp. 296–314, doi:10.1145/772062.772064.
  2. H-D. Ebbinghaus & J. Flum (1995): Finite Model Theory: First Edition. Springer Berlin Heidelberg, Berlin, Heidelberg, doi:10.1007/978-3-662-03182-7.
  3. L. C. Eggan (1963): Transition graphs and the star-height of regular events.. Michigan Math. J. 10(4), pp. 385–397, doi:10.1307/mmj/1028998975.
  4. A. Ehrenfeucht & P. Zeiger (1974): Complexity Measures for Regular Expressions. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC 74. Association for Computing Machinery, New York, NY, USA, pp. 7579, doi:10.1145/800119.803886.
  5. K. Ellul, B. Krawetz, J. Shallit & M. Wang (2005): Regular Expressions: New Results and Open Problems. J. Autom. Lang. Comb. 10(4), pp. 407437, doi:10.25596/jalc-2005-407.
  6. W. Gelade (2010): Succinctness of regular expressions with interleaving, intersection and counting. Theor. Comput. Sci. 411(31-33), pp. 2987–2998, doi:10.1016/j.tcs.2010.04.036.
  7. W. Gelade & F. Neven (2012): Succinctness of the Complement and Intersection of Regular Expressions. ACM Trans. Comput. Logic 13(1), doi:10.1145/2071368.2071372.
  8. H. Gruber & M. Holzer (2008): Finite Automata, Digraph Connectivity, and Regular Expression Size. In: L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir & I. Walukiewicz: Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Lecture Notes in Computer Science 5126. Springer, pp. 39–50, doi:10.1007/978-3-540-70583-3_4.
  9. H. Gruber & M. Holzer (2009): Tight Bounds on the Descriptional Complexity of Regular Expressions. In: V. Diekert & D. Nowotka: Developments in Language Theory. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 276–287, doi:10.1007/978-3-642-02737-6_22.
  10. K. Hashiguchi (1988): Algorithms for Determining Relative Star Height and Star Height. Inf. Comput. 78(2), pp. 124–169, doi:10.1016/0890-5401(88)90033-8.
  11. J. E. Hopcroft, R. Motwani & J. D. Ullman (2006): Introduction to Automata Theory, Languages, and Computation, 3rd edition. Addison-Wesley Longman Publishing Co., Inc., USA.
  12. R. McNaughton & S. A. Papert (1971): Counter-Free Automata (M.I.T. Research Monograph No. 65). The MIT Press.
  13. A. A. Razborov (1990): Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica 10(1), pp. 81–93, doi:10.1007/BF02122698.
  14. L. Stockmeyer (1974): The complexity of decision problems in automata theory and logic. Massachusetts Institute of Technology.
  15. Q. Yan (2007): Classifying regular languages by a split game. Theoretical Computer Science 374(1), pp. 181 – 190, doi:10.1016/j.tcs.2006.12.041.

Comments and questions to:
For website issues: