{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T06:55:34Z","timestamp":1777100134838,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540705826","type":"print"},{"value":"9783540705833","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70583-3_4","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"39-50","source":"Crossref","is-referenced-by-count":36,"title":["Finite Automata, Digraph Connectivity, and Regular Expression Size"],"prefix":"10.1007","author":[{"given":"Hermann","family":"Gruber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1007\/11672142_43","volume-title":"STACS 2006","author":"D. Berwanger","year":"2006","unstructured":"Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S.: Dag-width and parity games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 524\u2013536. Springer, Heidelberg (2006)"},{"key":"4_CR2","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-3-540-32275-7_15","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"D. Berwanger","year":"2005","unstructured":"Berwanger, D., Gr\u00e4del, E.: Entanglement\u2014A measure for the complexity of directed graphs with applications to logic and games. In: Baader, F., Voronkov, A. (eds.) LPAR 2004. LNCS (LNAI), vol.\u00a03452, pp. 209\u2013223. Springer, Heidelberg (2005)"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1007\/978-3-540-27836-8_21","volume-title":"Automata, Languages and Programming","author":"A. Bj\u00f6rklund","year":"2004","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Khanna, S.: Approximating longest directed paths and cycles. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 222\u2013233. Springer, Heidelberg (2004)"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF00263745","volume":"6","author":"R.V. Book","year":"1976","unstructured":"Book, R.V., Chandra, A.K.: Inherently nonplanar automata. Acta Informatica\u00a06, 89\u201394 (1976)","journal-title":"Acta Informatica"},{"key":"4_CR5","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. Michigan Mathematical Journal\u00a010, 385\u2013397 (1963)","journal-title":"Michigan Mathematical Journal"},{"issue":"2","key":"4_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":"4_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":"4_CR8","unstructured":"Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. In: Albers, S., Weil, P. (eds.) Symposium on Theoretical Aspects of Computer Science. Dagstuhl Seminar Proceedings, vol.\u00a008001, pp. 325\u2013336. IBFI (2008)"},{"key":"4_CR9","unstructured":"Gruber, H., Holzer, M.: Finite automata, digraph connectivity and regular expression size. Technical report, Technische Universit\u00e4t M\u00fcnchen (December 2007)"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/978-3-540-78499-9_20","volume-title":"Foundations of Software Science and Computation 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.) Foundations of Software Science and Computation Structures. LNCS, vol.\u00a04962, pp. 273\u2013286. Springer, Heidelberg (2008)"},{"issue":"2","key":"4_CR11","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1016\/0890-5401(88)90033-8","volume":"78","author":"K. Hashiguchi","year":"1988","unstructured":"Hashiguchi, K.: Algorithms for determining relative star height and star height. Information and Computation\u00a078(2), 124\u2013169 (1988)","journal-title":"Information and Computation"},{"key":"4_CR12","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)"},{"issue":"1","key":"4_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"},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T. Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. Journal of Combinatorial Theory, Series B\u00a082(1), 138\u2013154 (2001)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"3","key":"4_CR15","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1051\/ita:2005027","volume":"39","author":"D. Kirsten","year":"2005","unstructured":"Kirsten, D.: Distance desert automata and the star height problem. RAIRO \u2013 Theoretical Informatics and Applications\u00a039(3), 455\u2013509 (2005)","journal-title":"RAIRO \u2013 Theoretical Informatics and Applications"},{"key":"4_CR16","series-title":"Annals of Mathematics Studies","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: Shannon, C.E., McCarthy, J. (eds.) Automata Studies. Annals of Mathematics Studies, pp. 3\u201342. Princeton University Press, Princeton (1956)"},{"issue":"2","key":"4_CR17","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1006\/inco.1994.1098","volume":"115","author":"A.J. Mayer","year":"1994","unstructured":"Mayer, A.J., Stockmeyer, L.J.: Word problems \u2013 This time with interleaving. Information and Computation\u00a0115(2), 293\u2013311 (1994)","journal-title":"Information and Computation"},{"issue":"1\/2","key":"4_CR18","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0019-9958(67)90481-0","volume":"11","author":"R. McNaughton","year":"1967","unstructured":"McNaughton, R.: The loop complexity of pure-group events. Information and Control\u00a011(1\/2), 167\u2013176 (1967)","journal-title":"Information and Control"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0020-0255(69)80016-2","volume":"1","author":"R. McNaughton","year":"1969","unstructured":"McNaughton, R.: The loop complexity of regular events. Information Sciences\u00a01, 305\u2013328 (1969)","journal-title":"Information Sciences"},{"issue":"1","key":"4_CR20","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1002\/(SICI)1096-908X(199701)9:1<47::AID-SMR142>3.0.CO;2-V","volume":"9","author":"P.H. Morris","year":"1997","unstructured":"Morris, P.H., Gray, R.A., Filman, R.E.: Goto removal based on regular expressions. Journal of Software Maintenance\u00a09(1), 47\u201366 (1997)","journal-title":"Journal of Software Maintenance"},{"issue":"6","key":"4_CR21","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1016\/j.ejc.2005.01.010","volume":"27","author":"J. Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Tree-depth, subgraph coloring and homomorphism bounds. European Journal of Combinatorics\u00a027(6), 1022\u20131041 (2006)","journal-title":"European Journal of Combinatorics"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1145\/1109557.1109647","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"J. Obdr\u017e\u00e1lek","year":"2006","unstructured":"Obdr\u017e\u00e1lek, J.: Dag-width: Connectivity measure for directed graphs. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 814\u2013821. ACM Press, New York (2006)"},{"key":"4_CR23","unstructured":"Pinsker, M.S.: On the complexity of a concentrator. In: Annual Teletraffic Conference, pp. 318\/1\u2013318\/4 (1973)"},{"issue":"3","key":"4_CR24","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":"4_CR25","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)"},{"key":"4_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/11672142_35","volume-title":"STACS 2006","author":"G. Schnitger","year":"2006","unstructured":"Schnitger, G.: Regular expressions and NFAs without \u03b5-transitions. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 432\u2013443. Springer, Heidelberg (2006)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70583-3_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T04:23:36Z","timestamp":1620015816000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70583-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540705826","9783540705833"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70583-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}