{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T13:41:56Z","timestamp":1771854116222,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540857792","type":"print"},{"value":"9783540857808","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-85780-8_30","type":"book-chapter","created":{"date-parts":[[2008,9,9]],"date-time":"2008-09-09T05:23:54Z","timestamp":1220937834000},"page":"383-395","source":"Crossref","is-referenced-by-count":9,"title":["Provably Shorter Regular Expressions from Deterministic Finite Automata"],"prefix":"10.1007","author":[{"given":"Hermann","family":"Gruber","sequence":"first","affiliation":[]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"30_CR1","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"J.A. Brzozowski","year":"1964","unstructured":"Brzozowski, J.A.: Derivatives of regular expressions. Journal of the ACM\u00a011(4), 481\u2013494 (1964)","journal-title":"Journal of the ACM"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Chung, F.R.K.: Spectral Graph Theory. In: CBMS Regional Conference Series in Mathematics, vol.\u00a092. American Mathematical Society (1997)","DOI":"10.1090\/cbms\/092"},{"key":"30_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"4","key":"30_CR4","first-page":"455","volume":"7","author":"M. Domaratzki","year":"2002","unstructured":"Domaratzki, M.: State complexity of proportional removals. Journal of Automata, Languages and Combinatorics\u00a07(4), 455\u2013468 (2002)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"issue":"12","key":"30_CR5","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 Mathematics\u00a0308(12), 2396\u20132406 (2008)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"30_CR6","doi-asserted-by":"crossref","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. Journal of Computer and System Sciences\u00a012(2), 134\u2013146 (1976)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"30_CR7","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. Journal of Automata, Languages and Combinatorics\u00a010(4), 407\u2013437 (2005)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"30_CR8","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science","author":"W. Gelade","year":"2008","unstructured":"Gelade, W.: Succinctness of regular expressions with interleaving, intersection and counting. In: Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, Turo\u0144, Poland, August 2008. LNCS. Springer, Heidelberg (to appear, 2008)"},{"key":"30_CR9","unstructured":"Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. In: Albers, S., Weil, P. (eds.) Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 2008. Dagstuhl Seminar Proceedings, vol.\u00a008001, pp. 325\u2013336. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany (2008)"},{"key":"30_CR10","volume-title":"Proceedings of the 35th International Colloquium on 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., Damgaard, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walkuwiewicz, I. (eds.) Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Reykjavik, Iceland, July 2008. Springer, Heidelberg (2008)"},{"key":"30_CR11","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. (ed.) FOSSACS 2008. LNCS, vol.\u00a04962, pp. 273\u2013286. Springer, Heidelberg (2008)"},{"issue":"1-3","key":"30_CR12","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.tcs.2006.09.025","volume":"370","author":"Y.-S. Han","year":"2007","unstructured":"Han, Y.-S., Wood, D.: Obtaining shorter regular expressions from finite-state automata. Theoretical Computer Science\u00a0370(1-3), 110\u2013120 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"30_CR13","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/S0890-5401(03)00090-7","volume":"186","author":"L. Ilie","year":"2003","unstructured":"Ilie, L., Yu, S.: Follow automata. Information and Computation\u00a0186(1), 140\u2013162 (2003)","journal-title":"Information and Computation"},{"key":"30_CR14","first-page":"3","volume-title":"Automata Studies, Annals of Mathematics Studies","author":"S.C. Kleene","year":"1956","unstructured":"Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, Annals of Mathematics Studies, pp. 3\u201342. Princeton University Press, Princeton (1956)"},{"issue":"2","key":"30_CR15","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics\u00a036(2), 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"30_CR16","unstructured":"McIntosh, H.V.: REEX: A CONVERT program to realize the McNaughton-Yamada analysis algorithm. Technical Report AIM-153, MIT Artificial Intelligence Laboratory (January 1968)"},{"issue":"1","key":"30_CR17","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1109\/TEC.1960.5221603","volume":"9","author":"R. McNaughton","year":"1960","unstructured":"McNaughton, R., Yamada, H.: Regular expressions and state graphs for automata. IRA Transactions on Electronic Computers\u00a09(1), 39\u201347 (1960)","journal-title":"IRA Transactions on Electronic Computers"},{"key":"30_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/11605157_33","volume-title":"Implementation and Application of Automata","author":"J.J. Morais","year":"2006","unstructured":"Morais, J.J., Moreira, N., Reis, R.: Acyclic automata with easy-to-find short regular expressions. In: Farr\u00e9, J., Litovsky, I., Schmitz, S. (eds.) CIAA 2005. LNCS, vol.\u00a03845, pp. 349\u2013350. Springer, Heidelberg (2006)"},{"issue":"3","key":"30_CR19","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms\u00a07(3), 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"30_CR20","first-page":"436","volume":"48","author":"P. Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n, P.: On an extremal problem in graph theory (in Hungarian). Matematicko Fizicki Lapok\u00a048, 436\u2013452 (1941)","journal-title":"Matematicko Fizicki Lapok"},{"key":"30_CR21","unstructured":"Wood, D.: Theory of Computation. John Wilet & Sons (1987)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85780-8_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T17:07:18Z","timestamp":1674061638000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-85780-8_30"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540857792","9783540857808"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85780-8_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}