论文部分内容阅读
二元判定自动机是借助于判定方法而不是用布尔逻辑来耱解开关函数的有限状态时序机,二元判定时序机(简称BDMs)在高速可编程控制器中的应用十分重要。因为BDMs的有效工作速度远远超过了普通微机处理器的有效工作速度。本文首次论了BDM求解时序函数的能力,以前研究者所定义的BDM表明,从自动机的理论上讲它的求解能力不如确定性有限状态自动机(简称DFA)的能力强,然而,用输入控制对BDM扩展之后表明其求解能力与DFA等效,这样BDM就可以用于完成有限状态时序函数的计算,本文旨在根据所期望的情况时空复杂性分析用BDM