一句话：提出加权树自动机的权重归一化（pushing），用于最小化与等价性测试，并显著降低等价性测试复杂度。
本文为定义在交换半域上的加权树自动机引入一种称为 pushing 的权重归一化过程。该过程在非确定型加权树自动机上也保持所识别的加权树语言不变，但对自底向上确定型自动机尤其有用：通过精心选择需要重新分配的权重并进行归一化，可把最小化和等价性测试归约到相应的自底向上确定型无权树自动机问题。作者据此给出新的等价性测试，运行时间为 O((|M|+|M'|)·log(|Q|+|Q'|))，改进了此前 O(|M|·|M'|) 的最好界。
A weight normalization procedure, commonly called pushing, is introduced for weighted tree automata (wta) over commutative semifields. The normalization preserves the recognized weighted tree language even for nondeterministic wta, but it is most useful for bottom-up deterministic wta, where it can be used for minimization and equivalence testing. In both applications a careful selection of the weights to be redistributed followed by normalization allows a reduction of the general problem to the corresponding problem for bottom-up deterministic unweighted tree automata. This approach was already successfully used by Mohri and Eisner for the minimization of deterministic weighted string automata. Moreover, the new equivalence test for two wta $M$ and $M'$ runs in time $\mathcal O((\lvert M \rvert + \lvert M'\rvert) \cdot \log {(\lvert Q\rvert + \lvert Q'\rvert)})$, where $Q$ and $Q'$ are the states of $M$ and $M'$, respectively, which improves the previously best run-time $\mathcal O(\lvert M \rvert \cdot \lvert M'\rvert)$.
@article{paperbot437,
title = {Pushing for weighted tree automata},
author = {Thomas Hanneforth and Andreas Maletti and Daniel Quernheim},
journal = {Logical Methods in Computer Science},
volume = {Volume 14, Issue 1},
year = {2018},
doi = {10.23638/lmcs-14(1:5)2018}
}