一句话：在交换半环上给出加权交替自动机的 Nivat 型刻画，并联系多项式自动机与 ZERONESS 可判定性。
论文研究加权交替自动机（WAFA）的识别能力及其与其他自动机模型的关系。作者证明：当权重取自交换半环时，WAFA 的行为可分解为加权有限树自动机（WFTA）的行为与一个特定树同态的复合，由此得到 Nivat 型刻画。文章进一步考察封闭性，证明该类级数对同态之逆封闭、但对同态不封闭；并借助树上的加权 MSO 逻辑给出逻辑刻画。最后建立 WAFA 与多项式自动机（PA）的强联系：一个加权语言被 WAFA 识别当且仅当其反转被 PA 识别。利用 PA 的相应结果，作者证明以有理数为权重的 WAFA 的 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.
@article{paperbot2168,
title = {A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings},
author = {Gustav Grabolle},
journal = {Logical Methods in Computer Science},
volume = {Volume 19, Issue 4},
year = {2023},
doi = {10.46298/lmcs-19(4:27)2023}
}