{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,1]],"date-time":"2026-11-01T13:59:50Z","timestamp":1793541590803,"version":"4.5.0"},"reference-count":24,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2015,2]]},"abstract":"<jats:p> We investigate the state complexity of multiple unions and of multiple intersections for prefix-free regular languages. Prefix-free deterministic finite automata have their own unique structural properties that are crucial for obtaining state complexity upper bounds that are improved from those for general regular languages. We present a tight lower bound construction for k-union using an alphabet of size k + 1 and for k-intersection using a binary alphabet. We prove that the state complexity upper bound for k-union cannot be reached by languages over an alphabet with less than k symbols. We also give a lower bound construction for k-union using a binary alphabet that is within a constant factor of the upper bound. <\/jats:p>","DOI":"10.1142\/s0129054115500124","type":"journal-article","created":{"date-parts":[[2015,5,6]],"date-time":"2015-05-06T04:05:36Z","timestamp":1430885136000},"page":"211-227","source":"Crossref","is-referenced-by-count":2,"title":["State Complexity of <i>k<\/i>-Union and <i>k<\/i>-Intersection for 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"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[{"name":"School of Computing, Queen's University Kingston, Ontario K7L 3N6, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2015,5,5]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45526-4_6"},{"issue":"3","key":"p_2","first-page":"303","volume":"7","author":"Cmpeanu C.","year":"2002","journal-title":"Languages and Combinatorics"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25929-6_9"},{"issue":"4","key":"p_4","first-page":"455","volume":"7","author":"Domaratzki M.","year":"2002","journal-title":"Languages and Combinatorics"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.02.025"},{"issue":"2","key":"p_6","first-page":"217","volume":"9","author":"Domaratzki M.","year":"2004","journal-title":"Languages and Combinatorics"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.026"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.06.003"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.046"},{"issue":"1","key":"p_10","first-page":"75","volume":"83","author":"Gao Y.","year":"2008","journal-title":"Fundamenta Informaticae"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054108005838"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.054"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003133"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111008933"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.05.008"},{"key":"p_19","first-page":"1373","volume":"11","author":"Maslov A.","year":"1970","journal-title":"Soviet Mathematics Doklady"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48340-3_21"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410200100X"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.06.011"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.015"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.02.032"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107004917"},{"issue":"2","key":"p_29","first-page":"221","volume":"6","author":"Yu S.","year":"2001","journal-title":"Languages and Combinatorics"},{"key":"p_30","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\/s0129054115500124","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T18:05:16Z","timestamp":1565201116000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/s0129054115500124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2]]},"references-count":24,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2015,5,5]]},"published-print":{"date-parts":[[2015,2]]}},"alternative-id":["10.1142\/s0129054115500124"],"URL":"https:\/\/doi.org\/10.1142\/s0129054115500124","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2]]}}}