论文标题
在交替的nivat定理上，超过通勤的半度性
A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings
论文作者
论文摘要
本文将加权交替的有限自动机（WAFA），加权有限树自动机（WFTA）和多项式自动机（PA）连接了类别。 首先，我们研究了在运行语义中使用树在加权交替自动机中的使用，并证明可以将加权交替自动机的行为表征为加权有限树自动机的行为的组成和特定的树同构，如果重量是从交换性的semirative semirative semiring的。 基于此，我们为加权交替自动机提供了类似Nivat的表征。此外，我们表明，通过加权交替自动机识别的系列类别是在同态逆上关闭的，而不是同态。此外，我们给出了加权交替自动机的逻辑表征，该自动机使用了树木加权MSO逻辑。最后，我们研究了加权交替自动机和多项式自动机之间的牢固联系。我们证明：加权语言是通过多项式自动机识别的加权交替自动机识别的。使用对多项式自动机的相应结果，我们能够证明加权交替的自动机的zeroness问题，并从合理数字中取出的权重。
This paper connects the classes of weighted alternating finite automata (WAFA), weighted finite tree automata (WFTA), and polynomial automata (PA). First, we investigate the use of trees in the run semantics for weighted alternating automata and prove that the behavior of a weighted alternating automaton can be characterized as the composition of the behavior of a weighted finite tree automaton and a specific tree homomorphism, if weights are taken from a commutative semiring. Based on this, we give a Nivat-like characterization for weighted alternating automata. Moreover, we show that the class of series recognized by weighted alternating automata is closed under inverses of homomorphisms, but not under homomorphisms. Additionally, we give a logical characterization of weighted alternating automata, which uses weighted MSO logic for trees. Finally, we investigate the strong connection between weighted alternating automata and polynomial automata. We prove: A weighted language is recognized by a weighted alternating automaton iff its reversal in recognized by a polynomial automaton. Using the corresponding result for polynomial automata, we are able to prove that the ZERONESS problem for weighted alternating automata with weights taken from the rational numbers decidable.
