Transition Complexity of Incomplete DFAs

被引：12
作者：
Gao, Yuan [1 ]
Salomaa, Kai [2 ]
Yu, Sheng [1 ]
机构：
[1] Univ Western Ontario, Dept Comp Sci, London, ON N6A 5B7, Canada
[2] Queens Univ, Sch Comp, Kingston, ON K7L 3N6, Canada
来源：
FUNDAMENTA INFORMATICAE | 2011年 / 110卷 / 1-4期
基金：
加拿大自然科学与工程研究理事会;
关键词：
transition complexity; deterministic finite automaton; incomplete automaton; regular languages; Boolean operations; STATE COMPLEXITY; FINITE AUTOMATA; REGULAR LANGUAGES; OPERATIONS;
D O I：
10.3233/FI-2011-533
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We consider the transition complexity of regular languages based on the incomplete deterministic finite automata. We establish tight bounds for the transition complexity of Boolean operations, in the case of union the upper and lower bounds differ by a multiplicative constant two. We show that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity bounds turn out to be similar to the corresponding bounds for state complexity.
引用
收藏
页码：143 / 158
页数：16
相关论文
共 21 条
123