Büchi自动机的优化综述  

OVERVIEW ON OPTIMISING Büchi AUTOMATA

作　　者：袁志斌[1] 

机构地区：[1]广东商学院信息学院,广东广州510320

出　　处：《计算机应用与软件》2010年第6期32-34,88,共4页Computer Applications and Software

基　　金：国家自然科学基金(60203011);广东省自然科学基金(06023961);广东省教育厅自然科学基金重点项目(05Z013);广东商学院校级课题(53026535)

摘　　要：对Büchi自动机进行优化是提高基于自动机的模型检测效率的重要手段。对直接模拟关系、延迟模拟关系和公平模拟关系的概念,进行了比较,并探讨了基于这些模拟关系的自动机优化方法。基于左右语言的优化是完全基于自动机理论的优化方法,于是深入探讨了利用左右语言对Büchi自动机的优化绍方法。最后对未来的研究方向作了简要的介绍。Optimising Büchi automata is an important means in improving automata-based model checking efficiency.In this paper we compare three notions of simulation relationship：direct,delay,and fair,and study the approach for optimizing automata using those simulation relationships as the tool.The optimisation based on the left and right languages fully belongs to the optimisation method on the basis of automata theory.We thoroughly study the optimisation of the Büchi automata with the left and right languages.Finally,some research directions for future works are also discussed in brief.

关 键 词：BÜCHI自动机 模拟 左右语言 

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构]