@book(ASU86,
 author       = "A. Aho and R. Sethi and J. D. Ullman",
 year         = "1986",
 title        = "Compilers: Principles, Techniques, and Tools",
 publisher    = "Addison Wesley",
)
@book(AHU74,
 author       = "A. V. Aho and J. E. Hopcroft and J. D. Ullman",
 year         = "1974",
 title        = "The Design and Analysis of Computer Algorithms",
 publisher    = "Addision-Wesley",
)
@book(AhUl72,
 author       = "A. V. Aho and J. D. Ullman",
 year         = "1972",
 title        = "The Theory of Parsing, Translation and Compiling",
 volume       = "I",
 publisher    = "Prentice-Hall",
)
@article(An96,
 author       = "V. Antimirov",
 year         = "1996",
 title        = "Partial derivatives of regular expressions and finite automaton constructions",
 journal      = "Theoretical Computer Science",
 volume       = "155",
 number       = "2",
 pages        = "291--319",
 doi          = "10.1016/0304-3975(95)00182-4",
)
@inproceedings(Ar61,
 author       = "D. N. Arden",
 year         = "1961",
 title        = "Delayed-Logic and Finite-State Machines",
 editor       = "T. Mott",
 booktitle    = "Proceedings of the $1$st and $2$nd Annual Symposium on Switching Theory and Logical Design",
 publisher    = "American Institute of Electrical Engineers, New York",
 address      = "Detroit, Michigan, USA",
 pages        = "133--151",
 doi          = "10.1109/FOCS.1961.13",
)
@misc(ACT10,
 author       = "A. Asperti and C. Sacerdoti Coen and E. Tassi",
 year         = "2010",
 title        = "Regular Expressions, \textit {au point}",
 howpublished = "arXiv:1010.2604v1 [cs.FL]",
)
@article(BeSe86,
 author       = "G. Berry and R. Sethi",
 year         = "1986",
 title        = "From Regular Expressions to Deterministic Automata",
 journal      = "Theoretical Computer Science",
 volume       = "48",
 number       = "3",
 pages        = "117--126",
 doi          = "10.1016/0304-3975(86)90088-5",
)
@inproceedings(BiTh10,
 author       = "Ph. Bille and M. Thorup",
 year         = "2010",
 title        = "Regular Expression Matching with Multi-Strings and Intervals",
 editor       = "M. Charikar",
 booktitle    = "Proceedings of the $21$st Annual ACM-SIAM Symposium on Discrete Algorithms",
 publisher    = "Society for Industrial and Applied Mathematics",
 address      = "Austin, Texas, USA",
 pages        = "1297--1308",
 doi          = "10.1137/1.9781611973075.104",
)
@article(BoCh76,
 author       = "R. V. Book and A. K. Chandra",
 year         = "1976",
 title        = "Inherently Nonplanar Automata",
 journal      = "Acta Informatica",
 volume       = "6",
 number       = "1",
 pages        = "89--94",
 doi          = "10.1007/BF00263745",
)
@inproceedings(BMMR10,
 author       = "S. Broda and A. Machiavelo and N. Moreira and R. Reis",
 year         = "2010",
 title        = "On the Average Number of States of Partial Derivative Automata",
 editor       = "Y. Gao and H. Lu and S. Seki and S. Yu",
 booktitle    = "Proceedings of the $14$th International Conference Developments in Language Theory",
 series       = "LNCS",
 volume       = "6224",
 publisher    = "Springer",
 address      = "London, Ontario, Canada",
 pages        = "112--123",
 doi          = "10.1007/978-3-642-14455-4_12",
)
@article(BMMR12,
 author       = "S. Broda and A. Machiavelo and N. Moreira and R. Reis",
 year         = "2012",
 title        = "On the Average Size of {G}lushkov and Partial Derivative Automata",
 journal      = "International Journal of Foundations of Computer Science",
 volume       = "23",
 number       = "5",
 pages        = "969--984",
 doi          = "10.1142/S0129054112400400",
)
@article(BMMR14,
 author       = "S. Broda and A. Machiavelo and N. Moreira and R. Reis",
 year         = "2014",
 title        = "A Hitchhiker's Guide to Descriptional Complexity Through Analytic Combinatorics",
 journal      = "Theoretical Computer Science",
 volume       = "528",
 pages        = "85--100",
 doi          = "10.1016/j.tcs.2014.02.013",
)
@article(Br93,
 author       = "A. Br\"uggemann-Klein",
 year         = "1993",
 title        = "Regular Expressions into Finite Automata",
 journal      = "Theoretical Computer Science",
 volume       = "120",
 pages        = "197--213",
 doi          = "10.1016/0304-3975(93)90287-4",
)
@article(Br64,
 author       = "J. A. Brzozowski",
 year         = "1964",
 title        = "Derivatives of regular expressions",
 journal      = "Journal of the ACM",
 volume       = "11",
 pages        = "481--494",
 doi          = "10.1145/321239.321249",
)
@article(BrMcC63,
 author       = "J. A. Brzozowski and E. J. McCluskey",
 year         = "1963",
 title        = "Signal flow graph techniques for sequential circuit state diagrams",
 journal      = "IEEE Transactions on Computers",
 volume       = "C-12",
 number       = "2",
 pages        = "67--76",
 doi          = "10.1109/PGEC.1963.263416",
)
@article(CaZi00,
 author       = "P. Caron and D. Ziadi",
 year         = "2000",
 title        = "Characterization of {G}lushkov automata",
 journal      = "Theoretical Computer Science",
 volume       = "233",
 number       = "1--2",
 pages        = "75--90",
 doi          = "10.1016/S0304-3975(97)00296-X",
)
@article(COZ07,
 author       = "J.-M. Champarnaud and F. Ouardi and D. Ziadi",
 year         = "2007",
 title        = "Normalized Expressions and Finite Automata",
 journal      = "International Journal of Algebra and Computation",
 volume       = "17",
 number       = "1",
 pages        = "141--154",
 doi          = "10.1142/S021819670700355X",
)
@article(ChZi02,
 author       = "J.-M. Champarnaud and D. Ziadi",
 year         = "2002",
 title        = "Canonical derivatives, partial derivatives and finite automaton constructions",
 journal      = "Theoretical Computer Science",
 volume       = "289",
 number       = "1",
 pages        = "137--163",
 doi          = "10.1016/S0304-3975(01)00267-5",
)
@inproceedings(ChPa92,
 author       = "C.H. Chang and R. Paige",
 year         = "1992",
 title        = "From Regular Expressions to {DFA}'s Using Compressed {NFA}'s",
 editor       = "A. Apostolico and M. Chrochemore and Z. Galil and U. Manber",
 booktitle    = "Proceedings of the $3$rd Annual Symposium on Combinatorial Pattern Matching",
 series       = "LNCS",
 volume       = "644",
 publisher    = "Springer",
 address      = "Tucson, Arizon, USA",
 pages        = "90--110",
 doi          = "10.1007/3-540-56024-6_8",
)
@techreport(Ch10,
 author       = "H. Chen",
 year         = "2010",
 title        = "Finite Automata of Expressions in the Case of Star Normal Form and One-Unambiguity",
 type         = "Technical Report",
 number       = "ISCAS-LCS-10-11",
 institution  = "Chinese Academy of Sciences",
 address      = "Institute of Software, State Key Laboratory of COmputer Science, Beijing 100190 China",
)
@article(Ch86b,
 author       = "M. Chrobak",
 year         = "1986",
 title        = "Finite automata and unary languages",
 journal      = "Theoretical Computer Science",
 volume       = "47",
 pages        = "149--158",
 doi          = "10.1016/0304-3975(86)90142-8",
)
@book(Co71e,
 author       = "J. H. Conway",
 year         = "1971",
 title        = "Regular Algebra and Finite Machines",
 publisher    = "Chapman and Hall",
)
@inproceedings(DeMo04,
 author       = "M. Delgado and J. Morais",
 year         = "2004",
 title        = "Approximation to the Smallest Regular Expression for a Given Regular Language",
 editor       = "M. Domaratzki and A. Okhotin and K. Salomaa and S. Yu",
 booktitle    = "Proceedings of the $9$th Conference on Implementation and Application of Automata",
 series       = "LNCS",
 volume       = "3317",
 publisher    = "Springer",
 address      = "Kingston, Ontario, Canada",
 pages        = "312--314",
 doi          = "10.1007/978-3-540-30500-2_31",
)
@book(DuKo01,
 author       = "D.-Z. Du and K.-I. Ko",
 year         = "2001",
 title        = "Problem Solving in Automata, Languages, and Complexity",
 publisher    = "John Wiley \& Sons",
 doi          = "10.1002/0471224642",
)
@article(EdFa12,
 author       = "K. Edwards and G. Farr",
 year         = "2012",
 title        = "Improved Upper Bounds for Planarization and Series-Parallelization of Degree-Bounded Graphs",
 journal      = "The Electronic Journal of Combinatorics",
 volume       = "19",
 number       = "2",
 pages        = "\#P25",
)
@article(Eg63,
 author       = "L. C. Eggan",
 year         = "1963",
 title        = "Transition graphs and the star height of regular events",
 journal      = "Michigan Mathematical Journal",
 volume       = "10",
 pages        = "385--397",
 doi          = "10.1307/mmj/1028998975",
)
@article(EhZe76,
 author       = "A. Ehrenfeucht and H. P. Zeiger",
 year         = "1976",
 title        = "Complexity Measures for Regular Expressions",
 journal      = "Journal of Computer and System Sciences",
 volume       = "12",
 number       = "2",
 pages        = "134--146",
 doi          = "10.1016/S0022-0000(76)80034-7",
)
@article(EKSW04,
 author       = "K. Ellul and B. Krawetz and J. Shallit and M.-W. Wang",
 year         = "2004",
 title        = "Regular Expressions: New Results and Open Problems",
 journal      = "Journal of Automata, Languages and Combinatorics",
 volume       = "9",
 number       = "2/3",
 pages        = "233--256",
)
@book(FlSe09,
 author       = "Ph. Flajolet and R. Sedgewick",
 year         = "2009",
 title        = "Analytic Combinatorics",
 publisher    = "Cambridge University Press",
 doi          = "10.1017/CBO9780511801655",
)
@article(GSY11,
 author       = "Y. Gao and K. Salomaa and S. Yu",
 year         = "2011",
 title        = "Transition Complexity of Incomplete {DFA}s",
 journal      = "Fundamenta Informaticae",
 volume       = "110",
 number       = "1--4",
 pages        = "143--158",
)
@article(PLRA11,
 author       = "P. Garc{\'\i }a and D. L{\'o}pez and J. Ruiz and G. I. {\'A}lvarez",
 year         = "2011",
 title        = "From regular expressions to smaller {NFA}s",
 journal      = "Theoretical Computer Science",
 volume       = "412",
 pages        = "5802--5807",
 doi          = "10.1016/j.tcs.2011.05.058",
)
@inproceedings(Ga11,
 author       = "P. Gawrychowski",
 year         = "2011",
 title        = "Chrobak Normal Form Revisited, with Applications",
 editor       = "B. Bouchou-Markhoff and P. Caron and J.-M. Champarnaud and D. Maurel",
 booktitle    = "Proceedings of the $16$th Conference on Implementation and Application of Automata",
 series       = "LNCS",
 volume       = "6807",
 publisher    = "Springer",
 address      = "Blois, France",
 pages        = "142--153",
 doi          = "10.1007/978-3-642-22256-6_14",
)
@article(Ge03,
 author       = "V. Geffert",
 year         = "2003",
 title        = "Translation of binary regular expressions into nondeterministic {$\epsilon $}-free automata with {$O(n\qopname \relax o{log}n)$} transitions",
 journal      = "Journal of Computer and System Sciences",
 volume       = "66",
 number       = "3",
 pages        = "451--472",
 doi          = "10.1016/S0022-0000(03)00036-9",
)
@article(Ge10,
 author       = "W. Gelade",
 year         = "2010",
 title        = "Succintness of regular expressions with interleaving, intersection, and counting",
 journal      = "Theoretical Computer Science",
 volume       = "411",
 number       = "31--33",
 pages        = "2987--2998",
 doi          = "10.1016/j.tcs.2010.04.036",
)
@inproceedings(GeNe08,
 author       = "W. Gelade and F. Neven",
 year         = "2008",
 title        = "Succinctness of Complement and Intersection of Regular Expressions",
 editor       = "S. Albers and P. Weil",
 booktitle    = "Proceedings of the $25$th International Symposium on Theoretical Aspects of Compter Science",
 series       = "Leibniz International Proceedings in Informatics",
 volume       = "1",
 publisher    = "Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik, Dagstuhl, Germany",
 address      = "Bordeaux, France",
 pages        = "325--336",
)
@article(GPWZ04,
 author       = "D. Giammarresi and J.-L. Ponty and D. Wood and D. Ziadi",
 year         = "2004",
 title        = "A Characterization of Thompson Digraphs",
 journal      = "Discrete Applied Mathematics",
 volume       = "134",
 number       = "1--3",
 pages        = "317--337",
 doi          = "10.1016/S0166-218X(03)00299-3",
)
@inproceedings(GPW99,
 author       = "D. Giammarresi and J.-L. Pony and D. Wood",
 year         = "1999",
 title        = "Thompson Languages",
 editor       = "J. Karhum{\"a}ki and H. Maurer and G. P{\u a}un and G. Rozenberg",
 booktitle    = "Jewels are Forever: Contributions on Theoretical Computer Science in Honor of {A}rto {S}alomaa",
 publisher    = "Springer",
 pages        = "16--24",
 doi          = "10.1007/978-3-642-60207-8_2",
)
@article(Gl61,
 author       = "V. M. Glushkov",
 year         = "1961",
 title        = "The abstract theory of automata",
 journal      = "Russian Mathematics Surveys",
 volume       = "16",
 pages        = "1--53",
 doi          = "10.1070/RM1961v016n05ABEH004112",
)
@article(GKKLMW02,
 author       = "J. Goldstine and M. Kappes and C. M. R. Kintala and H. Leung and A. Malcher and D. Wotschke",
 year         = "2002",
 title        = "Descriptional Complexity of Machines with Limited Resources",
 journal      = "Journal of Universal Computer Science",
 volume       = "8",
 number       = "2",
 pages        = "193--234",
 doi          = "10.1142/9781848165458_0001",
)
@article(GKW90,
 author       = "J. Goldstine and C. M. R. Kintala and D. Wotschke",
 year         = "1990",
 title        = "On Measuring Nondeterminism in Regular Languages",
 journal      = "Information and Computation",
 volume       = "86",
 number       = "2",
 pages        = "179--194",
 doi          = "10.1016/0890-5401(90)90053-K",
)
@article(GLW92,
 author       = "J. Goldstine and H. Leung and D. Wotschke",
 year         = "1992",
 title        = "On the relation between amibuity and nondeterminism in finite automata",
 journal      = "Information and Computation",
 volume       = "100",
 pages        = "261--170",
 doi          = "10.1016/0890-5401(92)90014-7",
)
@inproceedings(GrGu10,
 author       = "H. Gruber and St. Gulan",
 year         = "2010",
 title        = "Simplifying Regular Expressions",
 editor       = "A. H. Dediu and H. Fernau and C. Mart{\'\i }n-Vide",
 booktitle    = "Proceedings of the $4$th International Conference Language and Automata Theory and Applications",
 series       = "LNCS",
 volume       = "6031",
 publisher    = "Springer",
 address      = "Trier, Germany",
 pages        = "285--296",
 doi          = "10.1007/978-3-642-13089-2_24",
)
@inproceedings(GrHo08,
 author       = "H. Gruber and M. Holzer",
 year         = "2008",
 title        = "Finite Automata, Digraph Connectivity, and Regular Expression Size",
 editor       = "L. Aceto and I. Damgaard and L. A. Goldberg and M. M. Halld{\'o}rsson and A. Ing{\'o}lfsd{\'o}ttir and I. Walkuwiewicz",
 booktitle    = "Proceedings of the $35$th International Colloquium on Automata, Languages and Propgramming",
 series       = "LNCS",
 volume       = "5126",
 publisher    = "Springer",
 address      = "Reykjavik, Iceland",
 pages        = "39--50",
 doi          = "10.1007/978-3-540-70583-3_4",
)
@inproceedings(GrHo08d,
 author       = "H. Gruber and M. Holzer",
 year         = "2008",
 title        = "Provably Shorter Regular Expressions from Deterministic Finite Automata (Extended Abstract)",
 editor       = "M. Ito and M. Toyama",
 booktitle    = "Proceedings of the $12$th International Conference Developments in Language Theory",
 series       = "LNCS",
 volume       = "5257",
 publisher    = "Springer",
 address      = "Kyoto, Japan",
 pages        = "383--395",
 doi          = "10.1007/978-3-540-85780-8_30",
)
@inproceedings(GrHo09b,
 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    = "Proceedings of the $13$th International Conference Developments in Language Theory",
 series       = "LNCS",
 volume       = "5583",
 publisher    = "Springer",
 address      = "Stuttgart, Germany",
 pages        = "276--287",
 doi          = "10.1007/978-3-642-02737-6_22",
)
@article(GrHo13,
 author       = "H. Gruber and M. Holzer",
 year         = "2013",
 title        = "Provably Shorter Regular Expressions From Finite Automata",
 journal      = "International Journal of Foundations of Computer Science",
 volume       = "24",
 number       = "8",
 pages        = "1255--1279",
 doi          = "10.1142/S0129054113500330",
)
@techreport(GrHo14,
 author       = "H. Gruber and M. Holzer",
 year         = "2014",
 title        = "Regular Expressions From Deterministic Finite Automata, Revisited",
 type         = "IFIG Research Report",
 number       = "1403",
 institution  = "Institut f\"ur Informatik",
 address      = "Justus-Liebig-Universit{\"a}t Gie\ss en, Arndtstr.~2, D-35392 Gie\ss en, Germany",
)
@inproceedings(GHT09,
 author       = "H. Gruber and M. Holzer and M. Tautschnig",
 year         = "2009",
 title        = "Short Regular Expressions from Finite Automata: Empirical Results",
 editor       = "S. Maneth",
 booktitle    = "Proceedings of the $14$th Conference on Implementation and Application of Automata",
 series       = "LNCS",
 volume       = "5642",
 publisher    = "Springer",
 address      = "Sydney, Australia",
 pages        = "188--197",
 doi          = "10.1007/978-3-642-02979-0_22",
)
@inproceedings(GrJo08,
 author       = "H. Gruber and J. Johannsen",
 year         = "2008",
 title        = "Tight Bounds on the Descriptional Complexity of Regular Expressions",
 editor       = "R. Amadio",
 booktitle    = "Proceedings of the $11$th Conference Foundations of Software Science and Computational Structures",
 series       = "LNCS",
 volume       = "4962",
 publisher    = "Springer",
 address      = "Budapest, Hungary",
 pages        = "273--286",
 doi          = "10.1007/978-3-540-78499-9_20",
)
@misc(GLS12,
 author       = "H. Gruber and J. Lee and J. Shallit",
 year         = "2012",
 title        = "Enumerating regular expressions and their languages",
 howpublished = "arXiv:1204.4982 [cs.FL]",
)
@inproceedings(GuFe08,
 author       = "St. Gulan and H. Fernau",
 year         = "2008",
 title        = "An Optimal Comstruction of Finite Automata From Regular Expressions",
 editor       = "R. Hariharan and M. Mukund and V. Vinay",
 booktitle    = "Proceedings of the $28$th Conference on Foundations of Software Technology and Theoretical Compter Science",
 series       = "Dagstuhl Seminar Proceedings",
 volume       = "08002",
 publisher    = "Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany",
 address      = "Bangalore, India",
 pages        = "211--222",
)
@article(HaMu00,
 author       = "Ch. Hagenah and A. Muscholl",
 year         = "2000",
 title        = "Computing {$\epsilon $}-free {NFA} from regular expressions in {$O(n\qopname \relax o{log}^2(n))$} time",
 journal      = "RAIRO--Informatique th{\'e}orique et Applications / Theoretical Informatics and Applications",
 volume       = "34",
 number       = "5",
 pages        = "257--277",
 doi          = "10.1051/ita:2000116",
)
@article(HaWo07,
 author       = "Y.-S. Hand and D. Wood",
 year         = "2007",
 title        = "Obtaining shorter regular expressions from finite-state automata",
 journal      = "Theoretical Computer Science",
 volume       = "370",
 number       = "1--3",
 pages        = "110--120",
 doi          = "10.1016/j.tcs.2006.09.025",
)
@article(Ha88a,
 author       = "K. Hashiguchi",
 year         = "1988",
 title        = "Algorithms for determining the relative star height and star height",
 journal      = "Information and Computation",
 volume       = "78",
 number       = "2",
 pages        = "124--169",
 doi          = "10.1016/0890-5401(88)90033-8",
)
@inproceedings(HoJa11,
 author       = "M. Holzer and S. Jakobi",
 year         = "2011",
 title        = "Chop Operations and Expressions: Descriptional Complexity Considerations",
 editor       = "G. Mauri and A. Leporati",
 booktitle    = "Proceedings of the $15$th International Conference Developments in Language Theory",
 series       = "LNCS",
 volume       = "6795",
 publisher    = "Springer",
 address      = "Milan, Italy",
 pages        = "264--275",
 doi          = "10.1007/978-3-642-22321-1_23",
)
@article(HoKu09a,
 author       = "M. Holzer and M. Kutrib",
 year         = "2009",
 title        = "Nondeterministic Finite Automata---Recent Results on the Descriptional and Computational Complexity",
 journal      = "International Journal of Foundations of Computer Science",
 volume       = "20",
 number       = "4",
 pages        = "563--580",
 doi          = "10.1142/S0129054109006747",
)
@inproceedings(HoKu10a,
 author       = "M. Holzer and M. Kutrib",
 year         = "2010",
 title        = "The Complexity of Regular(-Like) Expressions",
 editor       = "Y. Gao and H. Lu and S. Seki and S. Yu",
 booktitle    = "Proceedings of the $14$th International Conference Developments in Language Theory",
 series       = "LNCS",
 volume       = "6224",
 publisher    = "Springer",
 address      = "London, Ontario, Canada",
 pages        = "16--30",
 doi          = "10.1007/978-3-642-14455-4_3",
)
@inproceedings(HoKu10,
 author       = "M. Holzer and M. Kutrib",
 year         = "2010",
 title        = "Descriptional Complexity---An Introductory Survey",
 editor       = "C. Mart{\'\i }n-Vide",
 booktitle    = "Scientific Applications of Language Methods",
 publisher    = "World Scientific",
 pages        = "1--58",
 doi          = "10.1142/9781848165458_0001",
)
@inproceedings(HoKu10b,
 author       = "M. Holzer and M. Kutrib",
 year         = "2010",
 title        = "Descriptional Complexity of (Un)ambiguous Finite State Machines and Pushdown Automata",
 editor       = "A. Kucera and I. Potapov",
 booktitle    = "Proceedings of the $4$th Workshop on Reachability Problems",
 series       = "LNCS",
 volume       = "6227",
 publisher    = "Springer",
 address      = "Brno, Czech Republic",
 pages        = "1--23",
 doi          = "10.1007/978-3-642-15349-5_1",
)
@article(HoKu11,
 author       = "M. Holzer and M. Kutrib",
 year         = "2011",
 title        = "Descriptional and Computational Complexity of Finite Automata---A Survey",
 journal      = "Information and Computation",
 volume       = "209",
 number       = "3",
 pages        = "456--470",
 doi          = "10.1016/j.ic.2010.11.013",
)
@book(HoUl79,
 author       = "J. E. Hopcroft and J. D. Ullman",
 year         = "1979",
 title        = "Introduction to Automata Theory, Languages and Computation",
 publisher    = "Addison-Wesley",
)
@article(Hr02,
 author       = "J. Hromkovi{\v c}",
 year         = "2002",
 title        = "Descriptional Complexity of Finite Automata: Concepts and Open Problems",
 journal      = "Journal of Automata, Languages and Combinatorics",
 volume       = "7",
 number       = "4",
 pages        = "519--531",
)
@article(HKKSS02,
 author       = "J. Hromkovi{\v c} and J. Karhum\"aki and H. Klauck and G. Schnitger and S. Seibert",
 year         = "2002",
 title        = "Communication complexity method for measuring nondeterminism in finite automata",
 journal      = "Information and Computation",
 volume       = "172",
 number       = "2",
 pages        = "202--217",
 doi          = "10.1006/inco.2001.3069",
)
@inproceedings(HrSc05,
 author       = "J. Hromkovi{\v c} and G. Schnitger",
 year         = "2005",
 title        = "{NFA}s with and without $\epsilon $-transitions",
 editor       = "L. Caires and G. F. Italiano and L. Monteiro and C. Palamidessi and M. Yung",
 booktitle    = "Proceedings of the $32$nd International Colloquium Automata, Languages and Programming",
 series       = "LNCS",
 volume       = "3580",
 publisher    = "Springer",
 address      = "Lisbon, Portugal",
 pages        = "385--396",
 doi          = "10.1007/11523468_32",
)
@article(HSW01,
 author       = "J. Hromkovi{\v c} and S. Seibert and Th. Wilke",
 year         = "2001",
 title        = "Translating Regular Expressions into Small $\epsilon $-Free Automata",
 journal      = "Journal of Computer and System Sciences",
 volume       = "62",
 number       = "4",
 pages        = "565--588",
 doi          = "10.1006/jcss.2001.1748",
)
@article(IlYu03,
 author       = "L. Ilie and S. Yu",
 year         = "2003",
 title        = "Follow automata",
 journal      = "Information and Computation",
 volume       = "186",
 number       = "1",
 pages        = "140--162",
 doi          = "10.1016/S0890-5401(03)00090-7",
)
@article(Ki05,
 author       = "D. Kirsten",
 year         = "2005",
 title        = "Distance desert automata and the star height problem",
 journal      = "RAIRO--Informatique th{\'e}orique et Applications / Theoretical Informatics and Applications",
 volume       = "39",
 number       = "3",
 pages        = "455--509",
 doi          = "10.1051/ita:2005027",
)
@incollection(Kl56,
 author       = "S. C. Kleene",
 year         = "1956",
 title        = "Representation of events in nerve nets and finite automata",
 editor       = "C. E. Shannon and J. McCarthy",
 booktitle    = "Automata studies",
 series       = "Annals of mathematics studies",
 volume       = "34",
 publisher    = "Princeton University Press",
 pages        = "2--42",
)
@article(Le81a,
 author       = "E. Leiss",
 year         = "1981",
 title        = "The complexity of restricted regular expressions and the synthesis problem for finite automata",
 journal      = "Journal of Computer and System Sciences",
 volume       = "23",
 number       = "3",
 pages        = "348--254",
 doi          = "10.1016/0022-0000(81)90070-2",
)
@article(Le98a,
 author       = "H. Leung",
 year         = "1998",
 title        = "On Finite Automata with Limited Nondeterminism",
 journal      = "Acta Informatica",
 volume       = "35",
 number       = "7",
 pages        = "595--624",
 doi          = "10.1007/s002360050133",
)
@article(Le98,
 author       = "H. Leung",
 year         = "1998",
 title        = "Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata",
 journal      = "SIAM Journal on Computing",
 volume       = "27",
 number       = "4",
 pages        = "1073--1082",
 doi          = "10.1137/S0097539793252092",
)
@article(Le05,
 author       = "H. Leung",
 year         = "2005",
 title        = "Descriptional complexity of {NFA} of different ambiguity",
 journal      = "International Journal of Foundations of Computer Science",
 volume       = "16",
 number       = "5",
 pages        = "975--984",
 doi          = "10.1142/S0129054105003418",
)
@article(Li03,
 author       = "Y. Lifshits",
 year         = "2003",
 title        = "A lower bound on the size of {$\epsilon $}-free {NFA} corresponding to a regular expression",
 journal      = "Information Processing Letters",
 volume       = "85",
 number       = "6",
 pages        = "293--299",
 doi          = "10.1016/S0020-0190(02)00436-2",
)
@article(LRS04,
 author       = "S. Lombardy and Y. R{\'e}gis-Gianas and J. Sakarovitch",
 year         = "2004",
 title        = "Introducing {VAUCANSON}",
 journal      = "Theoretical Computer Science",
 volume       = "328",
 number       = "1--2",
 pages        = "77--96",
 doi          = "10.1016/j.tcs.2004.07.007",
)
@inproceedings(MMR13,
 author       = "E. Maia and N. Moreira and R. Reis",
 year         = "2013",
 title        = "Incomplete Transition Complexity of Basic Operations on Finite Languages",
 editor       = "S. Konstantinidis",
 booktitle    = "Proceedings of the $18$th International Conference on Implementation and Application of Automata",
 series       = "LNCS",
 volume       = "7982",
 publisher    = "Springer",
 address      = "Halifax, Nova Scotia, Canada",
 pages        = "349--356",
 doi          = "10.1007/978-3-642-39274-0_31",
)
@inproceedings(MMR13a,
 author       = "E. Maia and N. Moreira and R. Reis",
 year         = "2013",
 title        = "Incomplete Transition Complexity of Some Basic Operations",
 editor       = "P. v. Emde Boas and F. C. A. Groen and G. F. Italiano and J. R. Nawrocki and H. Sack",
 booktitle    = "Proceedings of the $39$th International Conference on Current Trends in Theory and Practice of Computer Science",
 series       = "LNCS",
 volume       = "7741",
 publisher    = "Springer",
 address      = "{\v S}pindler{\o u}v Ml{\' y}n, Czech Republic",
 pages        = "319--331",
)
@book(Ma74a,
 author       = "Z. Manna",
 year         = "1974",
 title        = "Mathematical Theory of Computation",
 publisher    = "McGraw-Hill",
)
@inproceedings(Ma02,
 author       = "A. Martinez",
 year         = "2002",
 title        = "Efficient Computation of Regular Expressions from Unary {NFA}s",
 editor       = "J. Dassow and M. Hoeberechts and H. J{\"u}rgensen and D. Wotschke",
 booktitle    = "Pre-Proceedings of the $4$th Workshop on Descriptional Complexity of Formal Systems",
 series       = "Report No.",
 volume       = "586",
 publisher    = "Department of Computer Science, The University of Western Ontario, Canada",
 address      = "London, Ontario, Canada",
 pages        = "216--230",
)
@techreport(McI68,
 author       = "H. V. McIntosh",
 year         = "1968",
 title        = "{REEX}: A {CONVERT} Program to Realize the {M}c{N}aughton-{Y}amada Analysis Algorithm",
 type         = "Technical Report",
 number       = "AIM-153",
 institution  = "MIT Artificial Intelligence Laboratory",
)
@article(McN67a,
 author       = "R. McNaughton",
 year         = "1967",
 title        = "The loop complexity of pure-group events",
 journal      = "Information and Control",
 volume       = "11",
 number       = "1--2",
 pages        = "167--176",
 doi          = "10.1016/S0019-9958(67)90481-0",
)
@article(McN69,
 author       = "R. McNaughton",
 year         = "1969",
 title        = "The loop complexity of regular events",
 journal      = "Information Sciences",
 volume       = "1",
 pages        = "305--328",
 doi          = "10.1016/S0020-0255(69)80016-2",
)
@book(McN82,
 author       = "R. McNaughton",
 year         = "1982",
 title        = "Elementary computability, formal languages, and automata",
 publisher    = "Prentice-Hall",
)
@article(McNYa60,
 author       = "Robert McNaughton and Hisao Yamada",
 year         = "1960",
 title        = "Regular expressions and state graphs for automata",
 journal      = "IRE Transactions on Electronic Computers",
 volume       = "EC-9",
 number       = "1",
 pages        = "39--47",
 doi          = "10.1109/TEC.1960.5221603",
)
@inproceedings(MeFi71,
 author       = "A. R. Meyer and M. J. Fischer",
 year         = "1971",
 title        = "Economy of description by automata, grammars, and formal systems",
 booktitle    = "Proceedings of the $12$th Annual Symposium on Switching and Automata Theory",
 publisher    = "IEEE Computer Society Press",
 pages        = "188--191",
 doi          = "10.1109/T-C.1971.223108",
)
@article(Mi66,
 author       = "B. G. Mirkin",
 year         = "1966",
 title        = "An Algorithm for Constructing a Base in a Language of Regular Expressions",
 journal      = "Engineering Cybernetics",
 volume       = "5",
 pages        = "110--116",
)
@article(Mo71,
 author       = "F. R. Moore",
 year         = "1971",
 title        = "On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata",
 journal      = "IEEE Transaction on Computing",
 volume       = "C-20",
 pages        = "1211--1219",
 doi          = "10.1109/T-C.1971.223108",
)
@inproceedings(MNR10,
 author       = "N. Moreira and D. Nabais and R. Reis",
 year         = "2010",
 title        = "State Elimination Ordering Strategies: Some Experimental Results",
 editor       = "I. McQuillan and G. Pighizzini",
 booktitle    = "Proceedings of the $12$th Workshop on Descriptional Complexity of Formal Systems",
 series       = "EPTCS",
 volume       = "31",
 address      = "Saskatoon, Saskatchewan, Canada",
 pages        = "139--148",
)
@article(MoRe09,
 author       = "N. Moreira and R. Reis",
 year         = "2009",
 title        = "Series-Parallel Automata and Short Regular Expressions",
 journal      = "Fundamenta Informaticae",
 volume       = "91",
 number       = "3--4",
 pages        = "611--629",
)
@inproceedings(Ni09,
 author       = "C. Nicaud",
 year         = "2009",
 title        = "On the Average Size of {G}lushov's Automaton",
 editor       = "A. H. Dediu and A. M. Ionescu and C. Mart{\'\i }n-Vide",
 booktitle    = "Proceedings of the $3$rd International Conference Language and Automata Theory and Applications",
 series       = "LNCS",
 volume       = "5457",
 publisher    = "Springer",
 address      = "Tarragona, Spain",
 pages        = "626--637",
 doi          = "10.1007/978-3-642-00982-2_53",
)
@inproceedings(NPR10,
 author       = "C. Nicaud and C. Pivoteau and B. Razet",
 year         = "2010",
 title        = "Average Analysis of {G}lushkov Automata under a {BST}-Like Model",
 editor       = "K. Lodaya and M. Mahajan",
 booktitle    = "Proceedings of the $30$th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science",
 series       = "Leibniz International Proceedings in Informatics",
 volume       = "8",
 publisher    = "Schloss Dagstuhl--Leibniz-Zentrum f\"ur Informatik, Dagstuhl, Germany",
 address      = "Chennai, India",
 pages        = "388--399",
)
@article(OtFe61,
 author       = "G. Ott and N. H. Feinstein",
 year         = "1961",
 title        = "Design of Sequential Machines From Their Regular Expressions",
 journal      = "Journal of the ACM",
 volume       = "8",
 number       = "4",
 pages        = "585--600",
 doi          = "10.1145/321088.321097",
)
@inproceedings(PSA13,
 author       = "A. Palioudakis and K. Salomaa and S. Akl",
 year         = "2013",
 title        = "Comparisons Between Measures of Nondeterminism on Finite Automata",
 editor       = "H. J{\"u}rgensen and R. Reis",
 booktitle    = "Proceedings of the $15$th International Workshop Descriptional Complexity of Formal Systems",
 series       = "LNCS",
 volume       = "8031",
 publisher    = "Springer",
 address      = "London, Ontario, Canada",
 pages        = "229--240",
 doi          = "10.1007/978-3-642-39310-5_21",
)
@inproceedings(PSA12,
 author       = "A. Palioudakis and K. Salomaa and S. G. Akl",
 year         = "2012",
 title        = "State Complexity and Limited Nondeterminism",
 editor       = "M. Kutrib and N. Moreira and R. Reis",
 booktitle    = "Proceedings of the $14$th Workshop on Descriptional Complexity of Formal Systems",
 series       = "LNCS",
 volume       = "7386",
 publisher    = "Springer",
 address      = "Braga, Portugal",
 pages        = "252--265",
 doi          = "10.1007/978-3-642-31623-4_20",
)
@article(RaSc59,
 author       = "M. O. Rabin and D. Scott",
 year         = "1959",
 title        = "Finite Automata and Their Decision Problems",
 journal      = "IBM Journal of Research and Development",
 volume       = "3",
 pages        = "114--125",
 doi          = "10.1147/rd.32.0114",
)
@article(RaIb89,
 author       = "B. Ravikumar and O. H. Ibarra",
 year         = "1989",
 title        = "Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation",
 journal      = "SIAM Journal on Computing",
 volume       = "18",
 number       = "6",
 pages        = "1263--1282",
 doi          = "10.1137/0218083",
)
@misc(RRSS14,
 author       = "F. Reidl and P. Rossmanith and F. S\'anchez Villaamil and S. Sikdar",
 year         = "2014",
 title        = "A Faster Parameterized Algorithm for Treedepth",
 howpublished = "arXiv:1401.7540v3 [cs.DS]",
)
@book(Sa09,
 author       = "J. Sakarovitch",
 year         = "2009",
 title        = "Elements of Automata Theory",
 publisher    = "Cambridge University Press",
 doi          = "10.1017/CBO9781139195218",
)
@inproceedings(Sch06,
 author       = "G. Schnitger",
 year         = "2006",
 title        = "Regular Expressions and {NFA}s Without {$\epsilon $}-Transitions",
 editor       = "B. Durand and W. Thomas",
 booktitle    = "Proceedings of the $23$th International Symposium on Theoretical Aspects of Computer Science",
 series       = "LNCS",
 volume       = "3884",
 publisher    = "Springer",
 address      = "Marseille, France",
 pages        = "432--443",
)
@book(SiSo88,
 author       = "S. Sippu and E. Soisalon-Soininen",
 year         = "1988",
 title        = "Parsing Theory, Volume {I}: Languages and Parsing",
 series       = "EATCS Monographs on Theoretical Computer Science",
 volume       = "15",
 publisher    = "Springer",
 doi          = "10.1007/978-3-642-61345-6",
)
@article(Th68,
 author       = "K. Thompson",
 year         = "1968",
 title        = "Regular Expression Search Algorithm",
 journal      = "Communications of the ACM",
 volume       = "11",
 number       = "6",
 pages        = "419--422",
 doi          = "10.1145/363347.363387",
)
@article(To09,
 author       = "A. W. To",
 year         = "2009",
 title        = "Unary finite automata vs. arithmetic progressions",
 journal      = "Information Processing Letters",
 volume       = "109",
 number       = "17",
 pages        = "1010--1014",
 doi          = "10.1016/j.ipl.2009.06.005",
)
@phdthesis(Wa95,
 author       = "B. W. Watson",
 year         = "1995",
 title        = "Taxonomies and Toolkits of Regular Language Algorithms",
 type         = "Ph{D} thesis",
 school       = "Eindhoven University of Technology, Department of Mathematics and Computer Science",
 address      = "Den Dolech 2, 5612 AZ Eindhoven, The Netherlands",
)
@article(Yu01,
 author       = "S. Yu",
 year         = "2001",
 title        = "State complexity of regular languages",
 journal      = "Journal of Automata, Languages and Combinatorics",
 volume       = "6",
 pages        = "221--234",
)