可逆加权树自动机  

On Reversible Weighted Tree Automata

作　　者：魏秀娟[1] 李永明[1] 

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

出　　处：《模糊系统与数学》2015年第4期125-134,共10页Fuzzy Systems and Mathematics

基　　金：国家自然科学基金资助项目(11271237;61228305);教育部博士点基金资助项目(200807180005)

摘　　要：提出可逆自下而上树自动机,可逆加权树自动机和弱可逆加权树自动机的概念,证明了Σ和交换半环S上的可逆加权树自动机所识别语言的全体关于标量乘法、Hadamard-Product运算封闭,Σ和交换半环S上可逆加权树自动机所识别的语言做和运算得到的树语言为弱可逆树语言,Σ和交换半环S上的可逆加权树语言包含任何形式为1α的树级数(其中α为Σ(0)中任意元),Σ和半域S上的任一可逆加权树自动机与Σ和半域S上的一有布尔根权的可逆加权树自动机等价,可逆树语言的可识别性在半环同态下保持,Σ和布尔半环B上可逆加权树自动机所识别语言(即树级数)的全体构成的集合的支集与Σ上可逆自下而上树自动机所识别语言的全体构成的集合是相等关系,Σ和正半环S上可逆加权树自动机所识别语言(即树级数)的全体构成的集合的支集包含在Σ上可逆自下而上树自动机所识别语言的全体构成的集合中等性质。This paper provides the notions of reversible bottom-up tree automata, reversible weighted tree automata and weak reversible weighted tree automata. We prove that the class of all tree series recognized by reversible weighted tree automata over ∑ and commutative semiring S is closed under scalar multiplication and Hadamard-product. The sum of reversible tree languages over ∑, and commutative semiring S is a weak reversible tree language. For all α∈∑（0）, lα belongs to the set of all tree series recognized by reversible weighted tree automata over ∑ and commutative semiring S. Every reversible weighted tree automaton over ∑ and semifield S is equivalent to a reversible weighted tree automaton with Boolean root weight over ∑ and semifield S. Recognizability of the reversible tree series is preserved under semiring homomorphisms. The support of the set of all tree series recognized by reversible weighted tree automata over ∑ and Boolean semiring B is equal to the set of all languages recognized by reversible bottom-up tree automata over ∑. The support of the set of all tree series recognized by reversible weighted tree automata over ∑ and positive semiring S belongs to the set of all languages recognized by reversible bottom-up tree automata over ∑.

关 键 词：可逆自动机 加权树自动机 Σ-代数 树级数 

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