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  - 
TY  - JOUR
A1  - Maletti, Andreas
A1  - Graehl, Jonathan
A1  - Hopkins, Mark
A1  - Knight, Kevin
T1  - The power of extended top-down tree transducers
N2  - Extended top-down tree transducers (transducteurs generalises descendants; see [A. Arnold and M. Dauchet, Bi- transductions de forets, in Proceedings of the 3rd International Colloquium on Automata, Languages and Programming, Edinburgh University Press, Edinburgh, 1976, pp. 74-86]) received renewed interest in the field of natural language processing. Here those transducers are extensively and systematically studied. Their main properties are identified and their relation to classical top-down tree transducers is exactly characterized. The obtained properties completely explain the Hasse diagram of the induced classes of tree transformations. In addition, it is shown that most interesting classes of transformations computed by extended top-down tree transducers are not closed under composition.
Y1  - 2009
UR  - http://epubs.siam.org/SICOMP/
U6  - https://doi.org/10.1137/070699160
SN  - 0097-5397
ER  -