TY  - JOUR
A1  - Hanneforth, Thomas
A1  - Maletti, Andreas
A1  - Quernheim, Daniel
T1  - Pushing for weighted tree automata
BT  - Dedicated to the memory of Zoltan Esik (1951-2016)
JF  - Logical Methods in Computer Science
N2  - 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 O((|M|+|M′|)⋅log(|Q|+|Q′|)), where Q and Q′ are the states of M and M′, respectively, which improves the previously best run-time O(|M|⋅|M′|).
KW  - pushing weighted tree automaton
KW  - minimization
KW  - equivalence testing
Y1  - 2018
U6  - https://doi.org/10.23638/LMCS-14(1:5)2018
SN  - 1860-5974
VL  - 14
IS  - 1
PB  - Logical Methods in Computer Science E V
CY  - Braunschweig
ER  -