State Complexity of Union and Intersection of Finite Languages

State Complexity of Union and Intersection of Finite Languages
复制标题

有限语言的并集和交集的状态复杂性

DOI：
10.1142/s0129054108005838
复制
发表时间：
2007
期刊：
--
影响因子：
--
通讯作者：
K. Salomaa
K. Salomaa
中科院分区：
--
文献类型：
--
作者：
Yo;K. Salomaa

文献摘要

被引文献

相似文献

我们研究了有限语言的并和交的状态复杂性。请注意，获得两个操作的紧边界的问题是开放的。基于有限语言的最小确定性有限状态自动机（DFA）的结构性质，我们计算了其上界。然后，我们表明，上界是紧的，如果我们有一个可变大小的字母表，可以依赖于输入DFA的大小。此外，我们证明了上界是不可达到的任何固定大小的字母表。
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.