{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:44Z","timestamp":1759639064030},"reference-count":13,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p> We investigate the state complexity of union and intersection for finite languages. Note that the problem of obtaining the tight bounds for both operations was open. First we compute upper bounds using structural properties of minimal deterministic finite-state automata for finite languages. Then, we show that the upper bounds are tight if we have a variable sized alphabet that can depend on the size of input deterministic finite-state automata. In addition, we prove that the upper bounds are unreachable for any fixed sized alphabet. <\/jats:p>","DOI":"10.1142\/s0129054108005838","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T10:27:20Z","timestamp":1212488840000},"page":"581-595","source":"Crossref","is-referenced-by-count":20,"title":["STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES"],"prefix":"10.1142","volume":"19","author":[{"given":"YO-SUB","family":"HAN","sequence":"first","affiliation":[{"name":"Intelligence and Interaction Research Center, Korea Institute of Science and Technology, P.O.BOX 131, Cheongryang, Seoul, Korea"}]},{"given":"KAI","family":"SALOMAA","sequence":"additional","affiliation":[{"name":"School of Computing, Queen's University, Kingston, Ontario K7L 3N6, Canada"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","series-title":"Lecture Notes in Computer Science 3845","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/11605157_10","author":"Claveirole T.","year":"2006"},{"key":"rf3","first-page":"455","volume":"7","author":"Domaratzki M.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"rf4","first-page":"217","volume":"9","author":"Domaratzki M.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"rf5","first-page":"233","volume":"9","author":"Ellul K.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002199"},{"volume-title":"Introduction to Automata Theory, Languages, and Computation","year":"1979","author":"Hopcroft J.","key":"rf10"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003133"},{"key":"rf13","unstructured":"A.\u00a0Maslov, Soviet Mathematics Doklady\u00a011 (1970)\u00a0pp. 1373\u20131375."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410200100X"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1994.1023"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"rf18","first-page":"221","volume":"6","author":"Yu S.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"rf19","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\/S0129054108005838","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:33:25Z","timestamp":1565138005000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108005838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":13,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1142\/S0129054108005838"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108005838","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}