{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T09:10:38Z","timestamp":1774775438656,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642029783","type":"print"},{"value":"9783642029790","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02979-0_22","type":"book-chapter","created":{"date-parts":[[2009,7,6]],"date-time":"2009-07-06T08:16:20Z","timestamp":1246868180000},"page":"188-197","source":"Crossref","is-referenced-by-count":3,"title":["Short Regular Expressions from Finite Automata: Empirical Results"],"prefix":"10.1007","author":[{"given":"Hermann","family":"Gruber","sequence":"first","affiliation":[]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Tautschnig","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"22_CR1","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.tcs.2007.07.029","volume":"387","author":"M. Almeida","year":"2007","unstructured":"Almeida, M., Moreira, N., Reis, R.: Enumeration and generation with a string automata representation. Theor. Comput. Sci.\u00a0387(2), 93\u2013102 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/978-3-540-30500-2_31","volume-title":"Implementation and Application of Automata","author":"M. Delgado","year":"2005","unstructured":"Delgado, M., Morais, J.: Approximation to the smallest regular expression for a given regular language. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol.\u00a03317, pp. 312\u2013314. Springer, Heidelberg (2005)"},{"issue":"12","key":"22_CR3","doi-asserted-by":"publisher","first-page":"2396","DOI":"10.1016\/j.disc.2007.05.007","volume":"308","author":"K. Edwards","year":"2008","unstructured":"Edwards, K., Farr, G.E.: Planarization and fragmentability of some classes of graphs. Discrete Math.\u00a0308(12), 2396\u20132406 (2008)","journal-title":"Discrete Math."},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1307\/mmj\/1028998975","volume":"10","author":"L.C. Eggan","year":"1963","unstructured":"Eggan, L.C.: Transition graphs and the star height of regular events. Mich. Math. J.\u00a010, 385\u2013397 (1963)","journal-title":"Mich. Math. J."},{"issue":"2","key":"22_CR5","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/S0022-0000(76)80034-7","volume":"12","author":"A. Ehrenfeucht","year":"1976","unstructured":"Ehrenfeucht, A., Zeiger, H.P.: Complexity measures for regular expressions. J. Comput. Syst. Sci.\u00a012(2), 134\u2013146 (1976)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"22_CR6","first-page":"407","volume":"10","author":"K. Ellul","year":"2005","unstructured":"Ellul, K., Krawetz, B., Shallit, J., Wang, M.: Regular expressions: New results and open problems. J. Autom. Lang. Comb.\u00a010(4), 407\u2013437 (2005)","journal-title":"J. Autom. Lang. Comb."},{"issue":"2","key":"22_CR7","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/05064299X","volume":"38","author":"U. Feige","year":"2008","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput.\u00a038(2), 629\u2013657 (2008)","journal-title":"SIAM J. Comput."},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/3-540-45089-0_31","volume-title":"Implementation and Application of Automata","author":"M. Frishert","year":"2003","unstructured":"Frishert, M., Cleophas, L.G., Watson, B.W.: The effect of rewriting regular expressions on their accepting automata. In: Ibarra, O.H., Dang, Z. (eds.) CIAA 2003, vol.\u00a02759, pp. 304\u2013305. Springer, Heidelberg (2003)"},{"key":"22_CR9","unstructured":"Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. In: STACS 2008. Dagstuhl Seminar Proceedings, vol.\u00a008001, pp. 325\u2013336. IBFI Schloss Dagstuhl (2008)"},{"key":"22_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-540-70583-3_4","volume-title":"Automata, Languages and Programming","author":"H. Gruber","year":"2008","unstructured":"Gruber, H., Holzer, M.: Finite automata, digraph connectivity, and regular expression size. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol.\u00a05126, pp. 39\u201350. Springer, Heidelberg (2008)"},{"key":"22_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/978-3-540-85780-8_30","volume-title":"Developments in Language Theory","author":"H. Gruber","year":"2008","unstructured":"Gruber, H., Holzer, M.: Provably shorter regular expressions from deterministic finite automata (extended abstract). In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol.\u00a05257, pp. 383\u2013395. Springer, Heidelberg (2008)"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/978-3-540-78499-9_20","volume-title":"Foundations of Software Science and Computational Structures","author":"H. Gruber","year":"2008","unstructured":"Gruber, H., Johannsen, J.: Optimal lower bounds on regular expression size using communication complexity. In: Amadio, R.M. (ed.) FOSSACS 2008. LNCS, vol.\u00a04962, pp. 273\u2013286. Springer, Heidelberg (2008)"},{"issue":"1-3","key":"22_CR13","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.tcs.2006.09.025","volume":"370","author":"Y. Han","year":"2007","unstructured":"Han, Y., Wood, D.: Obtaining shorter regular expressions from finite-state automata. Theor. Comput. Sci.\u00a0370(1-3), 110\u2013120 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR14","volume-title":"Introduction to automata theory, languages and computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages and computation. Addison-Wesley, Reading (1979)"},{"key":"22_CR15","first-page":"3","volume-title":"Automata studies","author":"S.C. Kleene","year":"1956","unstructured":"Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Automata studies, pp. 3\u201342. Princeton University Press, Princeton (1956)"},{"key":"22_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/3-540-44674-5_16","volume-title":"Implementation and Application of Automata","author":"V. Maout Le","year":"2001","unstructured":"Le Maout, V.: Cursors. In: Yu, S., P\u0103un, A. (eds.) CIAA 2000. LNCS, vol.\u00a02088, pp. 195\u2013207. Springer, Heidelberg (2001)"},{"key":"22_CR17","unstructured":"Morgan, K.: Approximation algorithms for the maximum induced planar and outerplanar subgraph problems. Bachelor with honors thesis, Monash University, Australia (2005)"},{"issue":"12","key":"22_CR18","doi-asserted-by":"publisher","first-page":"1534","DOI":"10.1093\/bioinformatics\/btl113","volume":"22","author":"Y. Ponty","year":"2006","unstructured":"Ponty, Y., Termier, M., Denise, A.: GenRGenS: software for generating random genomic sequences and structures. Bioinformatics\u00a022(12), 1534\u20131535 (2006)","journal-title":"Bioinformatics"},{"key":"22_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/11605157_2","volume-title":"Implementation and Application of Automata","author":"J. Sakarovitch","year":"2006","unstructured":"Sakarovitch, J.: The language, the expression, and the (small) automaton. In: Farr\u00e9, J., Litovsky, I., Schmitz, S. (eds.) CIAA 2005. LNCS, vol.\u00a03845, pp. 15\u201330. Springer, Heidelberg (2006)"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02979-0_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T21:48:16Z","timestamp":1552081696000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02979-0_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029783","9783642029790"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02979-0_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}