{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T03:55:04Z","timestamp":1778558104971,"version":"3.51.4"},"reference-count":16,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2016,11]]},"abstract":"<jats:p> It is well known that the resulting language obtained by inserting a regular language to a regular language is regular. We study the nondeterministic and deterministic state complexity of the insertion operation. Given two incomplete DFAs of sizes m and n, we give an upper bound <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\" altimg=\"eq-00001.gif\"><mml:mrow><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>m<\/mml:mi><mml:mo>+<\/mml:mo><mml:mn>2<\/mml:mn><mml:mo stretchy=\"false\">)<\/mml:mo><mml:mo>\u00b7<\/mml:mo><mml:msup><mml:mn>2<\/mml:mn><mml:mrow><mml:mi>m<\/mml:mi><mml:mi>n<\/mml:mi><mml:mo>\u2212<\/mml:mo><mml:mi>m<\/mml:mi><mml:mo>\u2212<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:msup><mml:mo>\u00b7<\/mml:mo><mml:msup><mml:mn>3<\/mml:mn><mml:mi>m<\/mml:mi><\/mml:msup><\/mml:mrow><\/mml:math> and find a lower bound for an asymp-totically tight bound. We also present the tight nondeterministic state complexity by a fooling set technique. The deterministic state complexity of insertion is <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\" altimg=\"eq-00002.gif\"><mml:mrow><mml:msup><mml:mn>2<\/mml:mn><mml:mrow><mml:mi>\u0398<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>m<\/mml:mi><mml:mi>n<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:mrow><\/mml:math> and the nondeterministic state complexity of insertion is precisely <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\" altimg=\"eq-00003.gif\"><mml:mrow><mml:mi>m<\/mml:mi><mml:mi>n<\/mml:mi><mml:mo>+<\/mml:mo><mml:mn>2<\/mml:mn><mml:mi>m<\/mml:mi><\/mml:mrow><\/mml:math>, where m and n are the size of input finite automata. We also consider the state complexity of insertion in the case where the inserted language is bifix-free or non-returning. <\/jats:p>","DOI":"10.1142\/s0129054116500349","type":"journal-article","created":{"date-parts":[[2017,1,24]],"date-time":"2017-01-24T05:57:32Z","timestamp":1485237452000},"page":"863-878","source":"Crossref","is-referenced-by-count":7,"title":["State Complexity of Insertion"],"prefix":"10.1142","volume":"27","author":[{"given":"Yo-Sub","family":"Han","sequence":"first","affiliation":[{"name":"Department of Computer Science, Yonsei University 50 Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea"}]},{"given":"Sang-Ki","family":"Ko","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Yonsei University 50 Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea"}]},{"given":"Timothy","family":"Ng","sequence":"additional","affiliation":[{"name":"School of Computing, Queen\u2019s University Kingston, Ontario K7L 3N6, Canada"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[{"name":"School of Computing, Queen\u2019s University Kingston, Ontario K7L 3N6, Canada"}]}],"member":"219","published-online":{"date-parts":[[2017,1,23]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90327-P"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.030"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90198-5"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-015-0245-y"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054108005838"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.054"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002199"},{"key":"p_13","first-page":"181","volume":"51","author":"Kari L.","year":"1993","journal-title":"Bulletin of the EATCS"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90230-5"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-010-9208-y"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.06.031"},{"key":"p_17","first-page":"1373","volume":"11","author":"Maslov A.","year":"1970","journal-title":"Soviet Mathematics Doklady"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410200100X"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1023\/B:NACO.0000006769.27984.23"},{"issue":"2","key":"p_23","first-page":"221","volume":"6","author":"Yu S.","year":"2001","journal-title":"Languages and Combinatorics"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054116500349","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T02:52:13Z","timestamp":1565146333000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054116500349"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11]]},"references-count":16,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2017,1,23]]},"published-print":{"date-parts":[[2016,11]]}},"alternative-id":["10.1142\/S0129054116500349"],"URL":"https:\/\/doi.org\/10.1142\/s0129054116500349","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11]]}}}