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