{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:42:02Z","timestamp":1742913722037,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319411132"},{"type":"electronic","value":"9783319411149"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-41114-9_12","type":"book-chapter","created":{"date-parts":[[2016,6,27]],"date-time":"2016-06-27T10:05:14Z","timestamp":1467021914000},"page":"153-167","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of Languages Resulting from the Concatenation Operation"],"prefix":"10.1007","author":[{"given":"Galina","family":"Jir\u00e1skov\u00e1","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Szabari","sequence":"additional","affiliation":[]},{"given":"Juraj","family":"\u0160ebej","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,28]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"1652","DOI":"10.1016\/j.ic.2007.07.001","volume":"205","author":"V Geffert","year":"2007","unstructured":"Geffert, V.: Magic numbers in the state hierarchy of finite automata. Inform. Comput. 205, 1652\u20131670 (2007)","journal-title":"Inform. Comput."},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1142\/S0129054112400084","volume":"23","author":"M Holzer","year":"2012","unstructured":"Holzer, M., Jakobi, S., Kutrib, M.: The magic number problem for subregular language families. Internat. J. Found. Comput. Sci. 23, 115\u2013131 (2012)","journal-title":"Internat. J. Found. Comput. Sci."},{"unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory and Computation. Addison-Wesley Publishing Company, Reading (1979)","key":"12_CR3"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/S0304-3975(00)00029-3","volume":"237","author":"K Iwama","year":"2000","unstructured":"Iwama, K., Kambayashi, Y., Takaki, K.: Tight bounds on the number of states of DFAs that are equivalent to $$n$$-state NFAs. Theoret. Comput. Sci. 237, 485\u2013494 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/S0304-3975(02)00891-5","volume":"301","author":"K Iwama","year":"2003","unstructured":"Iwama, K., Matsuura, A., Paterson, M.: A family of NFAs which need $$2^n-\\alpha $$ deterministic states. Theoret. Comput. Sci. 301, 451\u2013462 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1142\/S0129054105003133","volume":"16","author":"J Jir\u00e1sek","year":"2005","unstructured":"Jir\u00e1sek, J., Jir\u00e1skov\u00e1, G., Szabari, A.: State complexity of concatenation and complementation. Internat. J. Found. Comput. Sci. 16, 511\u2013529 (2005)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"12_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/978-3-540-85780-8_34","volume-title":"Developments in Language Theory","author":"G Jir\u00e1skov\u00e1","year":"2008","unstructured":"Jir\u00e1skov\u00e1, G.: On the state complexity of complements, stars, and reversals of regular languages. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 431\u2013442. Springer, Heidelberg (2008)"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/s00224-011-9318-7","volume":"49","author":"G Jir\u00e1skov\u00e1","year":"2011","unstructured":"Jir\u00e1skov\u00e1, G.: Concatenation of regular languages and descriptional complexity. Theory Comput. Syst. 49, 306\u2013318 (2011)","journal-title":"Theory Comput. Syst."},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1142\/S0129054111008076","volume":"22","author":"G Jir\u00e1skov\u00e1","year":"2011","unstructured":"Jir\u00e1skov\u00e1, G.: Magic numbers and ternary alphabet. Internat. J. Found. Comput. Sci. 22, 331\u2013344 (2011)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1007\/978-3-319-08846-4_17","volume-title":"Implementation and Application of Automata","author":"G Jir\u00e1skov\u00e1","year":"2014","unstructured":"Jir\u00e1skov\u00e1, G., Palmovsk\u00fd, M., \u0160ebej, J.: Kleene closure on regular and prefix-free languages. In: Holzer, M., Kutrib, M. (eds.) CIAA 2014. LNCS, vol. 8587, pp. 226\u2013237. Springer, Heidelberg (2014)"},{"key":"12_CR11","first-page":"1373","volume":"11","author":"AN Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Soviet Math. Doklady 11, 1373\u20131375 (1970)","journal-title":"Soviet Math. Doklady"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M Rabin","year":"1959","unstructured":"Rabin, M., Scott, D.: Finite automata and their decision problems. IBM Res. Develop. 3, 114\u2013129 (1959)","journal-title":"IBM Res. Develop."},{"key":"12_CR13","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"1997","unstructured":"Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997)"},{"key":"12_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/978-3-642-39310-5_25","volume-title":"Descriptional Complexity of Formal Systems","author":"J \u0160ebej","year":"2013","unstructured":"\u0160ebej, J.: Reversal on regular languages and descriptional complexity. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 265\u2013276. Springer, Heidelberg (2013)"},{"key":"12_CR15","first-page":"41","volume-title":"Handbook of Formal Languages","author":"Sheng Yu","year":"1997","unstructured":"Yu, S.: Regular languages, Chap. 2. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. I, pp. 41\u2013110. Springer, Heidelberg (1997)"},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S Yu","year":"1994","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexity of some basic operations on regular languages. Theoret. Comput. Sci. 125, 315\u2013328 (1994)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"1027","DOI":"10.1142\/S0129054105003455","volume":"16","author":"L Zijl","year":"2005","unstructured":"Zijl, L.: Magic numbers for symmetric difference NFAs. Internat. J. Found. Comput. Sci. 16, 1027 (2005)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/978-3-642-39310-5_26","volume-title":"Descriptional Complexity of Formal Systems","author":"K \u010cevorov\u00e1","year":"2013","unstructured":"\u010cevorov\u00e1, K.: Kleene star on unary regular languages. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 277\u2013288. Springer, Heidelberg (2013)"},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/978-3-319-08846-4_10","volume-title":"Implementation and Application of Automata","author":"K \u010cevorov\u00e1","year":"2014","unstructured":"\u010cevorov\u00e1, K., Jir\u00e1skov\u00e1, G., Kraj\u0148\u00e1kov\u00e1, I.: On the square of regular languages. In: Holzer, M., Kutrib, M. (eds.) CIAA 2014. LNCS, vol. 8587, pp. 136\u2013147. Springer, Heidelberg (2014)"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-41114-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:03:01Z","timestamp":1594598581000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-41114-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319411132","9783319411149"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-41114-9_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"28 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}