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.
H-D. Ebbinghaus & J. Flum (1995):
Finite Model Theory: First Edition.
Springer Berlin Heidelberg,
Berlin, Heidelberg,
doi:10.1007/978-3-662-03182-7.
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.
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.
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.
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.
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.
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.
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.
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.
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.
R. McNaughton & S. A. Papert (1971):
Counter-Free Automata (M.I.T. Research Monograph No. 65).
The MIT Press.
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.
L. Stockmeyer (1974):
The complexity of decision problems in automata theory and logic.
Massachusetts Institute of Technology.
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.
eptcs@eptcs.org