位置:成果数据库 > 期刊 > 期刊详情页
可逆加权树自动机
  • ISSN号:1001-7402
  • 期刊名称:《模糊系统与数学》
  • 时间:0
  • 分类:TP301[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]
  • 作者机构:[1]陕西师范大学数学与信息科学学院,陕西西安710119
  • 相关基金:国家自然科学基金资助项目(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 ∑.

同期刊论文项目
期刊论文 27 会议论文 1
同项目期刊论文
期刊信息
  • 《模糊系统与数学》
  • 中国科技核心期刊
  • 主管单位:国防科技大学
  • 主办单位:国防科技大学理学院 国防科技大学理学院
  • 主编:刘应明
  • 地址:湖南长沙国防科技大学理学院
  • 邮编:410073
  • 邮箱:fuzzysys@cfsm.cn
  • 电话:0731-84576220
  • 国际标准刊号:ISSN:1001-7402
  • 国内统一刊号:ISSN:43-1179/O1
  • 邮发代号:42-180
  • 获奖情况:
  • 美国《数学评论》(Mathematical Reviews)核心引...,中国科技论文统计源期刊,《中国科学引文数据库》来源期刊
  • 国内外数据库收录:
  • 美国数学评论(网络版),德国数学文摘,日本日本科学技术振兴机构数据库,中国中国科技核心期刊,中国北大核心期刊(2004版),中国北大核心期刊(2008版),中国北大核心期刊(2011版),中国北大核心期刊(2014版)
  • 被引量:8133