论文标题
关于符号有限状态自动机的复杂性
On the Complexity of Symbolic Finite-State Automata
论文作者
论文摘要
我们重新审查了SFA上的程序的复杂性（例如交点，空虚等），并根据我们发现的措施分析适合符号自动机的措施：状态的最大过渡次数以及最复杂的过渡性谓词的大小。我们关注SFA的特殊形式：{归一化的SFA}和{Neat SFAS}，以及在{Monotonic}有效的布尔代数上的SFA。
We revisit the complexity of procedures on SFAs (such as intersection, emptiness, etc.) and analyze them according to the measures we find suitable for symbolic automata: the number of states, the maximal number of transitions exiting a state, and the size of the most complex transition predicate. We pay attention to the special forms of SFAs: {normalized SFAs} and {neat SFAs}, as well as to SFAs over a {monotonic} effective Boolean algebra.
