爱华网
要：首先在格值逻辑框架下引入格值自动机的概念,并提出可逆映射的概念,从而诱导出格值可逆自动机的概念;其次研究了格值可逆自动机的代数性质,同时给出保证该代数性质成立的充分必要条件.
Abstract:Firstly, the notion lattice-valued automaton is introduced in the frame of lattice-valued logic, and the concept of reversible mapping is given, which induced the notion of lattice-valued reversible automaton at the same time; Secondly, the author establish the algebraic properties of lattice-valued reversible automata, and present the necessary and sufficient condition that guarantee these algebraic properties hold in the mean time.
关键词：格值逻辑；格值自动机；格值可逆自动机；代数性质
Key words:lattice-valued logic；lattice-valued automata；lattice-valued reversible automaton；algebraic property
中图分类号：TP301.1;O153.1文献标识码：A 文章编号：1006-4311（2011）23-0156-02
1前言
有穷自动机作为计算理论中最简单的数学模型,它不仅是计算机科学的理论基础,为现代计算理论提供可靠的形式理论,而且与神经网络、数学模型等领域密切相关,在汇编语言、编译语言和算法设计等方面有重要的应用[4,6,7]。但在处理自然语言尤其是人类使用的语言时,形式语言对于人类使用语言的模糊性的描述能力明显不够.为此，1965年，Zadeh LA[8,16,19]等人提出了模糊语言的概念,1969年,Wee WG利用模糊集的方法研究自动机理论[16-17]，模糊自动机为计算理论提供了一种研究和处理包含模糊性自然语言的有力工具,关于模糊自动机和模糊语言的讨论已有很多[9-18].在[11]中Mordeson JN开始了模糊自动机的代数研究，Asveld PRJ，等人在[1]较详细地研究了模糊自动机的代数性质.随后李永明,邱道文,应明生[9-10,13-14,18]等人不同程度地推广了模糊自动机理论,并提供了多值逻辑意义下研究自动机理论的方法，其势必将拉近形式语言和自然语言之间的距离.当强调对于环境资源的消耗问题,亦即资源的权值，就得到了更广泛的基于词的计算模型――加权自动机模型，其在模型检测，文本搜索，时态逻辑，图像压缩和语音处理等领域的应用已成为近期热点问题[3]。本文旨在进一步探索取值于一般有界格的-值自动机的代数性质，主要针对自动机的可逆性展开研究。
参考文献:
[1]Asveld P R J.Algebraic aspects of families of fuzzy languages[J]. Theoretical Computer Science，2003，293:417-445.
[2]Birkhoff G.Lattice Theory[M].Third Edition，Amer.Math.Soc，Providence， Rhode Island，USA，1973.
[3]Droste M，Kuich W，Vogler H.Handbook ofWeighted Automata. EATCS Monographs in Theoretical Computer Science. Springer-Verlag，2009.
[4]Eilenberg S.Automata，Languages and Machines[M]，Vol.A，B.Academic Press，New York，1974，1976.
[5]Hájek P. Metamathematics of Fuzzy Logic[M]， Dordrecht: Kluwer Academic Publisher，1998.
[6]Hopcroft J E，Ullman J D.Introduction to Automata Theory，Languages and Computation[M].Addson-Wesley，New York，1979.
[7]Khoussainov B.Nerode A.Automata Theory and its Applications[M]. Boston:Birk user，2001.
[8]Lee E T，Zadeh L A.Note on fuzzy languages[J]. Information Sciences 1（1969）421-434.
[9]Li Y M，Pedrycz W.Fuzzy finite automata and fuzzy regular expressions with memebership values in lattice-ordered monoids[J].Fuzzy Sets and Systems， 2005，156:68-92.
[10]Li Y M.Finite automata theory with membership values in lattices[J]. Information Sciences181（2011）1003-1017.
[11]Mordeson J N，Malik D S.Fuzzy and languages:Theory and Applications[M].Chapman& Hall / CRC，Boca Paton，London，2002.
[12]Shen J Z.Fuzzy language on free monoid[J].Information Sciences，1996. 88 149-168.
[13]邱道文.基于完备剩余格值逻辑的自动机理论-I.拓扑刻画[J].中国科学（E），2003，33（2）:137-146.
[14]邱道文.基于完备剩余格值逻辑的自动机理论-II.可逆性及同态[J].中国科学（E），2003，33（4）:340-349.
[15]Wechler W.The Concept of Fuzziness in Automata and Language Theory[M].Addison-Wesley，Reading，MA，USA，1978.
[16]Wee W G.On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification[D]. Ph. D. Thesis，Purdue University，June 1967.
[17]Wee W G，Fu K S.A formulation of fuzzy automata and its application as a model of learning systems[J].IEEE Trans.Systems Man Cybernet，1969，5:215-223.
[18]Ying M. S. A theory of computation based on quantum logic（I）[J]. Theoretical Computer Science，2005，344:134-207.
[19]Zadeh L A.Fuzzy sets[J].Information and control，1965，8:338-353.
百度搜索“爱华网”,专业资料、生活学习,尽在爱华网!
