模糊Büchi自动机的等价刻画  

Equivalent Characterizations of Fuzzy Büchi Automata

作　　者：韩召伟[1,2] 李永明[2] 

机构地区：[1]陕西师范大学数学与信息科学学院,西安710062 [2]陕西师范大学计算机科学学院,西安710062

出　　处：《计算机学报》2013年第6期1235-1245,共11页Chinese Journal of Computers

基　　金：国家自然科学基金(11271237;11226266);陕西师范大学科研启动基金(999553)资助~~

摘　　要：模糊语言的研究是形式语言研究的焦点之一,然而如何对模糊语言进行刻画甚至更好地分类是其中一个重要研究方向.文章在模糊ω-语言的研究基础上,从模糊逻辑角度研究了模糊ω-正则语言的等价刻画.首先借助广义子集构造方法,证明了任一模糊Büchi自动机与具有分明初始状态和状态转移函数且具有模糊终状态的模糊Büchi自动机是等价的,藉此研究了模糊ω-正则语言的代数刻画和层次刻画,讨论了模糊ω-正则语言关于正则运算的封闭性;其次引入单体二阶Lukasiewicz逻辑的概念,给出模糊Büchi自动机识别语言的等价逻辑刻画;最后通过引入ω-星自由和ω-非周期模糊ω-语言,利用'层次化'处理技巧得到了多值逻辑意义下的分类定理,对模糊ω-正则语言给出了一种分类方法.The study of fuzzy languages is one of the noticed focus in the formal language research, however how to characterize all fuzzy languages and even better sort them in some hier- archy is an important area in this field. In this paper, based on the current studies of fuzzy ω-languages, the authors mainly dealt with the equivalent characterizations of fuzzy ω-regular languages in the frame of fuzzy logic setting. Firstly, by dint of general subset-construction methods, the authors proved the fact that an arbitrary fuzzy Büchi automaton and the one with crisp initial states and transition function but with fuzzy final states are mutually equivalent. Based on this, they investigated the algebraic and level characterizations of fuzzy ω-regular languages, and also discussed the closed properties of fuzzy ω-regular languages under standard operations at the same time. Secondly, by introducing the concept of monadic second-order Lukasiewicz logic, the authors presented the equivalent logic characterization of fuzzy ω-regular languages which is recognized by a given fuzzy Btichi automaton. Finally, the notions of first- order Lukasiewicz logic, ω-star-free fuzzy ω-language and ω-aperiodic fuzzy ω-language were pro- vided, and by dint of ＂levelization＂ processing techniques the classification theorem in fuzzy logic setting was obtained, which constitutes a sorting scheme of fuzzy ω-regular languages.

关 键 词：模糊逻辑 模糊Büchi自动机 模糊ω-正则语言 单体二阶Lukasiewicz逻辑 刻画 

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