{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T12:34:27Z","timestamp":1725798867575},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319096971"},{"type":"electronic","value":"9783319096988"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09698-8_4","type":"book-chapter","created":{"date-parts":[[2014,8,18]],"date-time":"2014-08-18T00:52:51Z","timestamp":1408323171000},"page":"37-48","source":"Crossref","is-referenced-by-count":0,"title":["State Complexity of Deletion"],"prefix":"10.1007","author":[{"given":"Yo-Sub","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sang-Ki","family":"Ko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","first-page":"303","volume":"7","author":"C. C\u00e2mpeanu","year":"2002","unstructured":"C\u00e2mpeanu, C., Salomaa, K., Yu, S.: Tight lower bound for the state complexity of shuffle of regular languages. J. Autom. Lang. Comb.\u00a07, 303\u2013310 (2002)","journal-title":"J. Autom. Lang. Comb."},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.tcs.2012.02.030","volume":"437","author":"B. Cui","year":"2012","unstructured":"Cui, B., Gao, Y., Kari, L., Yu, S.: State complexity of combined operations with two basic operations. Theoret. Comput. Sci.\u00a0437, 98\u2013107 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.tcs.2004.02.031","volume":"320","author":"M. Domaratzki","year":"2004","unstructured":"Domaratzki, M.: Deletion along trajectories. Theoret. Comput. Sci.\u00a0320, 293\u2013313 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"2377","DOI":"10.1016\/j.tcs.2009.02.025","volume":"410","author":"M. Domaratzki","year":"2009","unstructured":"Domaratzki, M., Okhotin, A.: State complexity of power. Theoret. Comput. Sci.\u00a0410, 2377\u20132392 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR5","first-page":"217","volume":"9","author":"M. Domaratzki","year":"2004","unstructured":"Domaratzki, M., Salomaa, K.: State complexity of shuffle on trajectories. J. Automata, Languages and Combinatorics\u00a09, 217\u2013232 (2004)","journal-title":"J. Automata, Languages and Combinatorics"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tcs.2013.09.014","volume":"510","author":"H.-S. Eom","year":"2013","unstructured":"Eom, H.-S., Han, Y.-S.: State complexity of combined oeprations for suffix-free regular languages. Theoret. Comput. Sci.\u00a0510, 87\u201393 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-642-39310-5_7","volume-title":"Descriptional Complexity of Formal Systems","author":"H.-S. Eom","year":"2013","unstructured":"Eom, H.-S., Han, Y.-S., Jir\u00e1skov\u00e1, G.: State complexity of basic operations on non-returning regular languages. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol.\u00a08031, pp. 54\u201365. Springer, Heidelberg (2013)"},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-642-39310-5_9","volume-title":"Descriptional Complexity of Formal Systems","author":"H.-S. Eom","year":"2013","unstructured":"Eom, H.-S., Han, Y.-S., Salomaa, K.: State complexity of k-union and k-intersection for prefix-free regular languages. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol.\u00a08031, pp. 78\u201389. Springer, Heidelberg (2013)"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.tcs.2013.06.003","volume":"499","author":"Y. Gao","year":"2013","unstructured":"Gao, Y., Kari, L.: State complexity of star of union and square of union on k regular languages. Theoret. Comput. Sci.\u00a0499, 38\u201350 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR10","unstructured":"Gao, Y., Piao, X.: State complexity of insertion, manuscript in preparation (2014)"},{"issue":"5","key":"4_CR11","doi-asserted-by":"publisher","first-page":"1085","DOI":"10.1142\/S0129054112400461","volume":"23","author":"Y. Gao","year":"2012","unstructured":"Gao, Y., Yu, S.: State complexity and approximation. Int. J. Found. Comput. Sci.\u00a023(5), 1085\u20131098 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"2537","DOI":"10.1016\/j.tcs.2008.12.054","volume":"410","author":"Y.-S. Han","year":"2009","unstructured":"Han, Y.-S., Salomaa, K.: State complexity of basic operations on suffix-free regular languages. Theoret. Comput. Sci.\u00a0410, 2537\u20132548 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.ic.2010.11.013","volume":"209","author":"M. Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata \u2014 A survey. Inf. Comput.\u00a0209, 456\u2013470 (2011)","journal-title":"Inf. Comput."},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1142\/S0129054105003133","volume":"16","author":"J. Jir\u00e1sek","year":"2005","unstructured":"Jir\u00e1sek, J., Jir\u00e1skova, G., Szabari, A.: State complexity of concatenation and complementation. Internat. J. Foundations Comput. Sci.\u00a016, 511\u2013529 (2005)","journal-title":"Internat. J. Foundations Comput. Sci."},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/978-3-642-31653-1_34","volume-title":"Developments in Language Theory","author":"G. Jir\u00e1skov\u00e1","year":"2012","unstructured":"Jir\u00e1skov\u00e1, G., Shallit, J.: The state complexity of star-complement-star. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol.\u00a07410, pp. 380\u2013391. Springer, Heidelberg (2012)"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0304-3975(94)90230-5","volume":"132","author":"L. Kari","year":"1994","unstructured":"Kari, L.: On language equations with invertible operations. Theoret. Comput. Sci.\u00a0132, 129\u2013150 (1994)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR17","unstructured":"Kari, L.: On insertion and deletion in formal languages. PhD thesis. University of Turku (1991)"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1080\/00207169408804288","volume":"52","author":"L. Kari","year":"1994","unstructured":"Kari, L.: Deletion operations: Closure properties. Internat. J. Comput. Math.\u00a052, 23\u201342 (1994)","journal-title":"Internat. J. Comput. Math."},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2004.09.038","volume":"332","author":"L. Kari","year":"2005","unstructured":"Kari, L., Sosik, P.: Aspects of shuffle and deletion on trajectories. Theoret. Comput. Sci.\u00a0332, 47\u201361 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR20","first-page":"70","volume":"111","author":"M. Kutrib","year":"2013","unstructured":"Kutrib, M., Pighizzini, G.: Recent trends in descriptional complexity of formal languages. Bulletin of the EATCS\u00a0111, 70\u201386 (2013)","journal-title":"Bulletin of the EATCS"},{"key":"4_CR21","first-page":"328","volume":"9","author":"O.B. Lupanov","year":"1963","unstructured":"Lupanov, O.B.: A comparison of two types of finite sources. Problemy Kibernetiki\u00a09, 328\u2013335 (1963)","journal-title":"Problemy Kibernetiki"},{"key":"4_CR22","first-page":"1373","volume":"11","author":"A.N. Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates on the number of states of finite automata. Soviet Math. Dokl.\u00a011, 1373\u20131375 (1970)","journal-title":"Soviet Math. Dokl."},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars and formal systems. In: Proc. SWAT (FOCS), pp. 188\u2013191. IEEE Computer Society (1971)","DOI":"10.1109\/SWAT.1971.11"},{"key":"4_CR24","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"C-20","author":"F.R. Moore","year":"1971","unstructured":"Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Transactions on Computers\u00a0C-20, 1211\u20131214 (1971)","journal-title":"IEEE Transactions on Computers"},{"key":"4_CR25","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.ipl.2005.06.011","volume":"98","author":"N. Rampersad","year":"2006","unstructured":"Rampersad, N.: The state complexity of L\n                  2 and L\n                  \n                    k\n                  . Inform. Proc. Letters\u00a098, 231\u2013234 (2006)","journal-title":"Inform. Proc. Letters"},{"key":"4_CR26","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/j.tcs.2007.04.015","volume":"383","author":"A. Salomaa","year":"2007","unstructured":"Salomaa, A., Salomaa, K., Yu, S.: State complexity of combined operations. Theoret. Comput. Sci.\u00a0383, 140\u2013152 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511808876"},{"key":"4_CR28","unstructured":"Wood, D.: Theory of Computation. John Wiley & Sons, Inc., New York (1987)"},{"key":"4_CR29","doi-asserted-by":"crossref","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a0I, pp. 41\u2013110. Springer (1997)","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"4_CR30","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 complexities of some basic operations on regular languages. Theoret. Comput. Sci.\u00a0125, 315\u2013328 (1994)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09698-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T16:25:25Z","timestamp":1558974325000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-09698-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319096971","9783319096988"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09698-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}