{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:59Z","timestamp":1759638779465},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,6,16]],"date-time":"2015-06-16T00:00:00Z","timestamp":1434412800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00236-015-0245-y","type":"journal-article","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T10:11:54Z","timestamp":1434363114000},"page":"67-85","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["State complexity of deletion and bipolar deletion"],"prefix":"10.1007","volume":"53","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","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"key":"245_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. 7, 303\u2013310 (2002)","journal-title":"J. Autom. Lang. Comb."},{"key":"245_CR2","doi-asserted-by":"crossref","unstructured":"Cho, D.-J., Han, Y.-S., Ko, S.-K., Salomaa, K.: State complexity ofinversion operations. In: Proceedings of the DCFS 2014. Lecture Notes in Computer Science, vol. 8614. Springer, Berlin, pp. 102\u2013113 (2014)","DOI":"10.1007\/978-3-319-09704-6_10"},{"key":"245_CR3","first-page":"98","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. Theor. Comput. Sci. 437, 98\u2013107 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR4","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/j.tcs.2004.02.031","volume":"320","author":"M Domaratzki","year":"2004","unstructured":"Domaratzki, M.: Deletion along trajectories. Theor. Comput. Sci. 320, 293\u2013313 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR5","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 410, 2377\u20132392 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR6","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1016\/j.tcs.2005.07.013","volume":"345","author":"M Domaratzki","year":"2005","unstructured":"Domaratzki, M., Salomaa, K.: Decidability of trajectory-based equations. Theor. Comput. Sci. 345, 304\u2013330 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR7","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 510, 87\u201393 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR8","doi-asserted-by":"crossref","unstructured":"Eom, H.-S., Han, Y.-S., Jir\u00e1skova, G.: State complexity of basicoperations on non-returning regular languages. In: Proceedings of the DCFS 2013. Lecture Notes in Computer Science, vol. 8031. Springer, Berlin, pp. 54\u201365 (2013)","DOI":"10.1007\/978-3-642-39310-5_7"},{"key":"245_CR9","doi-asserted-by":"crossref","unstructured":"Eom, H.-S., Han, Y.-S., Salomaa, K.: State complexity of $$k$$ k -unionand $$k$$ k -intersection for prefix-free regular languages. In: Proceedings of the DCFS 2013. Lecture Notes in Computer Science, vol. 8031. Springer, Berlin, pp. 78\u201389 (2013)","DOI":"10.1007\/978-3-642-39310-5_9"},{"key":"245_CR10","doi-asserted-by":"crossref","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$$ k regular languages. Theor. Comput. Sci. 499, 38\u201350 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR11","unstructured":"Gao, Y., Moreira, N., Reis, R., Yu, S.: A Review on State Complexity of Individual Operations. Technical report DCC-2011-8, Faculdade de Ciencias, Universidade do Porto. www.dcc.fc.up.pt\/dcc\/Pubs\/TReports\/TR11\/dcc-2011-08 (to appear in Computer Science Review)"},{"key":"245_CR12","unstructured":"Gao, Y., Piao, X.: State Complexity of Insertion (manuscript in preparation) (2014)"},{"issue":"5","key":"245_CR13","doi-asserted-by":"crossref","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. 23(5), 1085\u20131098 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"245_CR14","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 410, 2537\u20132548 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR15","doi-asserted-by":"crossref","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\u2014a survey. Inf. Comput. 209, 456\u2013470 (2011)","journal-title":"Inf. Comput."},{"key":"245_CR16","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/j.tcs.2004.04.010","volume":"327","author":"M Holzer","year":"2004","unstructured":"Holzer, M., K\u00f6nig, B.: On deterministic finite automata and syntactic monoid size. Theor. Comput. Sci. 327, 319\u2013347 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR17","doi-asserted-by":"crossref","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. Int. J. Found. Comput. Sci. 16, 511\u2013529 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"245_CR18","doi-asserted-by":"crossref","unstructured":"Jir\u00e1skova, G., Shallit, J.: The state complexity of star-complement-star. In: Yen, H.-C., Ibarra, O.H. (eds.) Developments in Language Theory. Lecture Notes in Computer Science, vol. 7410. Springer, Berlin, pp. 380\u2013391 (2012)","DOI":"10.1007\/978-3-642-31653-1_34"},{"key":"245_CR19","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 132, 129\u2013150 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR20","unstructured":"Kari, L.: On Insertion and Deletion in Formal Languages. Ph.D. thesis, University of Turku (1991)"},{"key":"245_CR21","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1080\/00207169408804288","volume":"52","author":"L Kari","year":"1994","unstructured":"Kari, L.: Deletion operations: closure properties. Int. J. Comput. Math. 52, 23\u201342 (1994)","journal-title":"Int. J. Comput. Math."},{"key":"245_CR22","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 332, 47\u201361 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR23","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1142\/S0129054105003157","volume":"13","author":"B Krawetz","year":"2005","unstructured":"Krawetz, B., Lawrence, J., Shallit, J.: State complexity and the monoid of transformations of a finite set. Int. J. Found. Comput. Sci. 13, 547\u2013563 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"245_CR24","first-page":"70","volume":"111","author":"M Kutrib","year":"2013","unstructured":"Kutrib, M., Pighizzini, G.: Recent trends in descriptional complexity of formal languages. Bull. EATCS 111, 70\u201386 (2013)","journal-title":"Bull. EATCS"},{"key":"245_CR25","doi-asserted-by":"crossref","unstructured":"Lavado, G.J., Pighizzini, G., Seki, S.: Operational state complexity under Parikh equivalence. In: Proceedings of the DCFS \u201914. Lecture Notes in Computer Science, vol. 8614. Springer, berlin pp. 294\u2013305 (2014)","DOI":"10.1007\/978-3-319-09704-6_26"},{"key":"245_CR26","first-page":"328","volume":"9","author":"OB Lupanov","year":"1963","unstructured":"Lupanov, O.B.: A comparison of two types of finite sources. Probl. Kibern. 9, 328\u2013335 (1963)","journal-title":"Probl. Kibern."},{"key":"245_CR27","first-page":"1373","volume":"11","author":"AN Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates on the number of states of finite automata. Sov. Math. Dokl. 11, 1373\u20131375 (1970)","journal-title":"Sov. Math. Dokl."},{"key":"245_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00163-1","volume":"197","author":"A Mateescu","year":"1998","unstructured":"Mateescu, A., Rozenberg, G., Salomaa, A.: Shuffle on trajectories: syntactic constraints. Theor. Comput. Sci. 197, 1\u201356 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR29","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars and formal systems. In: Proceedings of the SWAT (FOCS). IEEE Computer Society, Northridge, California, pp. 188\u2013191 (1971)","DOI":"10.1109\/SWAT.1971.11"},{"key":"245_CR30","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"C\u201320","author":"FR 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 Trans. Comput. C\u201320, 1211\u20131214 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"245_CR31","doi-asserted-by":"crossref","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^2$$ L 2 and $$L^k$$ L k . Inf. Proc. Lett. 98, 231\u2013234 (2006)","journal-title":"Inf. Proc. Lett."},{"key":"245_CR32","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 383, 140\u2013152 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR33","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.tcs.2004.02.032","volume":"320","author":"A Salomaa","year":"2004","unstructured":"Salomaa, A., Wood, D., Yu, S.: On the state complexity of reversals of regular languages. Theor. Comput. Sci. 320, 315\u2013329 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"245_CR34","volume-title":"A Second Course in Formal Languages and Automata Theory","author":"J Shallit","year":"2009","unstructured":"Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009)"},{"key":"245_CR35","volume-title":"Theory of Computation","author":"D Wood","year":"1987","unstructured":"Wood, D.: Theory of Computation. Wiley, New York (1987)"},{"key":"245_CR36","doi-asserted-by":"crossref","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. I, pp. 41\u2013110. Springer, Berlin (1997)","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"245_CR37","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 125, 315\u2013328 (1994)","journal-title":"Theor. Comput. Sci."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-015-0245-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-015-0245-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-015-0245-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,27]],"date-time":"2019-08-27T00:07:42Z","timestamp":1566864462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-015-0245-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,16]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["245"],"URL":"https:\/\/doi.org\/10.1007\/s00236-015-0245-y","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,16]]}}}