可逆加权树自动机

摘要：

提出可逆自下而上树自动机,可逆加权树自动机和弱可逆加权树自动机的概念,证明了∑和交换半环S上的可逆加权树自动机所识别语言的全体关于标量乘法、Hadamard-Product运算封闭,∑和交换半环S上可逆加权树自动机所识别的语言做和运算得到的树语言为弱可逆树语言,∑和交换半环S上的可逆加权树语言包含任何形式为1α的树级数(其中α为∑(0)中任意元),∑和半域S上的任一可逆加权树自动机与∑和半域S上的一有布尔根权的可逆加权树自动机等价,可逆树语言的可识别性在半环同态下保持,∑和布尔半环B上可逆加权树自动机所识别语言(即树级数)的全体构成的集合的支集与∑上可逆自下而上树自动机所识别语言的全体构成的集合是相等关系,∑和正半环S上可逆加权树自动机所识别语言(即树级数)的全体构成的集合的支集包含在∑上可逆自下而上树自动机所识别语言的全体构成的集合中等性质.

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

所属期刊栏目：29

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;高等学校博士学科点专项科研基金

在线出版日期：2015-11-05（万方平台首次上网日期，不代表论文的发表时间）

页码：125-134