{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T18:51:16Z","timestamp":1784227876876,"version":"3.55.0"},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p> Recently, researchers studied the state complexity of boundary \u2014 [Formula: see text] \u2014 of regular languages L motivated from the famous Kuratowski\u2019s 14-theorem. Prefix codes \u2014 a set of languages \u2014 play an important role in several applications. We consider prefix-free regular languages and investigate the state complexity of two operations, [Formula: see text] and [Formula: see text] for prefix-free regular languages. Based on the unique structural properties of a prefix-free minimal DFA, we compute the precise state complexity of [Formula: see text] and [Formula: see text]. We then present the tight bound over a quaternary alphabet for [Formula: see text] and [Formula: see text]. Our results are smaller than the composition of the state complexity function for individual operations of prefix-free regular languages. <\/jats:p>","DOI":"10.1142\/s0129054115500392","type":"journal-article","created":{"date-parts":[[2015,11,6]],"date-time":"2015-11-06T05:33:42Z","timestamp":1446788022000},"page":"697-707","source":"Crossref","is-referenced-by-count":4,"title":["State Complexity of Boundary of Prefix-Free Regular Languages"],"prefix":"10.1142","volume":"26","author":[{"given":"Hae-Sung","family":"Eom","sequence":"first","affiliation":[{"name":"Department of Computer Science, Yonsei University, 50, Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yo-Sub","family":"Han","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Yonsei University, 50, Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2015,11,6]]},"reference":[{"issue":"3","key":"p_2","first-page":"303","volume":"7","author":"Cmpeanu C.","year":"2002","journal-title":"Languages and Combinatorics"},{"issue":"4","key":"p_4","first-page":"455","volume":"7","author":"Domaratzki M.","year":"2002","journal-title":"Languages and Combinatorics"},{"issue":"2","key":"p_5","first-page":"217","volume":"9","author":"Domaratzki M.","year":"2004","journal-title":"Languages and Combinatorics"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.026"},{"issue":"1","key":"p_7","first-page":"75","volume":"83","author":"Gao Y.","year":"2008","journal-title":"Fundamenta Informaticae"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054108005838"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.054"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003133"},{"key":"p_14","first-page":"1373","volume":"11","author":"Maslov A.","year":"1970","journal-title":"Soviet Mathematics Doklady"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410200100X"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.015"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.02.032"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107004917"},{"issue":"2","key":"p_22","first-page":"221","volume":"6","author":"Yu S.","year":"2001","journal-title":"Languages and Combinatorics"},{"key":"p_23","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\/S0129054115500392","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T14:03:54Z","timestamp":1565100234000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054115500392"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":15,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2015,11,6]]},"published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.1142\/S0129054115500392"],"URL":"https:\/\/doi.org\/10.1142\/s0129054115500392","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9]]}}}