TY - GEN
T1 - State complexity of union and intersection of finite languages
AU - Han, Yo Sub
AU - Salomaa, Kai
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=34548080408&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34548080408&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-73208-2_22
DO - 10.1007/978-3-540-73208-2_22
M3 - Conference contribution
AN - SCOPUS:34548080408
SN - 3540732071
SN - 9783540732075
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 217
EP - 228
BT - Developments in Language Theory - 11th International Conference, DLT 2007 Proceedings
PB - Springer Verlag
T2 - 11th International Conference on Developments in Language Theory, DLT 2007
Y2 - 3 July 2007 through 6 July 2007
ER -