{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T03:06:23Z","timestamp":1725505583321},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540784975"},{"type":"electronic","value":"9783540784999"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78499-9_20","type":"book-chapter","created":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T19:02:25Z","timestamp":1207076545000},"page":"273-286","source":"Crossref","is-referenced-by-count":17,"title":["Optimal Lower Bounds on Regular Expression Size Using Communication Complexity"],"prefix":"10.1007","author":[{"given":"Hermann","family":"Gruber","sequence":"first","affiliation":[]},{"given":"Jan","family":"Johannsen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","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":"2","key":"20_CR2","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":"20_CR3","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":"20_CR4","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1006\/jcss.1995.1033","volume":"50","author":"M. Grigni","year":"1995","unstructured":"Grigni, M., Sipser, M.: Monotone separation of logarithmic space from logarithmic depth. Journal of Computer and System Sciences\u00a050, 433\u2013437 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR5","unstructured":"Gruber, H., Holzer, M.: Finite automata, digraph connectivity and regular expression size. Technical report, Technische Universit\u00e4t M\u00fcnchen (December 2007)"},{"issue":"1\u20133","key":"20_CR6","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. Theoretical Computer Science\u00a0370(1\u20133), 110\u2013120 (2007)","journal-title":"Theoretical Computer Science"},{"key":"20_CR7","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":"20_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M. Karchmer","year":"1990","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics\u00a03, 255\u2013265 (1990)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1007\/BF01747074","volume":"10","author":"V.M. Khrapchenko","year":"1972","unstructured":"Khrapchenko, V.M.: Methods for determining lower bounds for the complexity of \u03c0-schemes (English translation). Math. Notes Acad. Sciences USSR\u00a010, 474\u2013479 (1972)","journal-title":"Math. Notes Acad. Sciences USSR"},{"key":"20_CR10","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)"},{"key":"20_CR11","volume-title":"Communication complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, New York (1997)"},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70918-3_13","volume-title":"STACS 2007","author":"T. Lee","year":"2007","unstructured":"Lee, T.: A new rank technique for formula size lower bounds. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, Springer, Heidelberg (2007)"},{"key":"20_CR13","unstructured":"Martinez, A.: Efficient computation of regular expressions from unary NFAs. In: Dassow, J., Hoeberechts, M., J\u00fcrgensen, H., Wotschke, D. (eds.) Workshop on Descriptional Complexity of Formal Systems 2002, London, Canada, pp. 216\u2013230 (2002)"},{"issue":"1","key":"20_CR14","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":"20_CR15","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: IEEE Symposium on Switching and Automata Theory 1971, pp. 188\u2013191 (1971)","DOI":"10.1109\/SWAT.1971.11"},{"key":"20_CR16","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":"1","key":"20_CR17","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"},{"key":"20_CR18","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) automation. In: Farr\u00e9, J., Litovsky, I., Schmitz, S. (eds.) CIAA 2005. LNCS, vol.\u00a03845, pp. 15\u201330. Springer, Heidelberg (2006)"},{"issue":"1","key":"20_CR19","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1145\/321312.321326","volume":"13","author":"A. Salomaa","year":"1966","unstructured":"Salomaa, A.: Two complete axiom systems for the algebra of regular events. Journal of the ACM\u00a013(1), 158\u2013169 (1966)","journal-title":"Journal of the ACM"},{"key":"20_CR20","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)"},{"key":"20_CR21","first-page":"142","volume":"76","author":"S. Yu","year":"2002","unstructured":"Yu, S.: State complexity of finite and infinite regular languages. Bulletin of the EATCS\u00a076, 142\u2013152 (2002)","journal-title":"Bulletin of the EATCS"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computational Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78499-9_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:11:30Z","timestamp":1619507490000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78499-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540784975","9783540784999"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78499-9_20","relation":{},"subject":[]}}