Han, Yo-Sub Salomaa, Kai 2024-01-20T23:04:03Z 2024-01-20T23:04:03Z 2022-01-25 2008-06 0129-0541 https://pubs.kist.re.kr/handle/201004/133408 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. English WORLD SCIENTIFIC PUBL CO PTE LTD REGULAR LANGUAGES BASIC OPERATIONS State complexity of union and intersection of finite languages Article 10.1142/S0129054108005838 1 INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, v.19, no.3, pp.581 - 595 INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 19 3 581 595 scie scopus 000256383100006 2-s2.0-44849090524 Computer Science, Theory & Methods Computer Science Article; Proceedings Paper REGULAR LANGUAGES BASIC OPERATIONS state complexity finite-state automata finite languages