提出可逆自下而上树自动机,可逆加权树自动机和弱可逆加权树自动机的概念,证明了∑和交换半环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 ∑.