Han, Yo-Sub Salomaa, Kai 2024-01-19T13:38:47Z 2024-01-19T13:38:47Z 2022-03-07 2007 0302-9743 https://pubs.kist.re.kr/handle/201004/116421 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. We compute the upper bounds based on the structural properties of minimal deterministic finite-state automata (DFAs) 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 DFAs. In addition, we prove that the upper bounds are unreachable for any fixed sized alphabet. English SPRINGER-VERLAG BERLIN State complexity of union and intersection of finite languages Conference 1 11th International Conference on Developments in Language Theory, v.4588, pp.217 - + 11th International Conference on Developments in Language Theory 4588 217 + GE Univ Turku, Turku, FINLAND 2007-07-03 DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS 000247909100022 2-s2.0-34548080408 Proceedings Paper