Pushing for weighted tree automata

作     者：Hanneforth, Thomas Maletti, Andreas Quernheim, Daniel 

作者机构：Universität Potsdam Human Sciences Faculty Department Linguistik Karl-Liebknecht-Str. 24–25 Potsdam14476 Germany Universität Leipzig Faculty of Mathematics and Computer Science Institute of Computer Science PO box 100 920 Leipzig04009 Germany Universität Stuttgart Institute for Natural Language Processing Pfaffenwaldring 5b Stuttgart70569 Germany 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2017年

核心收录：

主　　题：Automata theory 

摘      要：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′|).MSC Codes 68Q45, 68Q25 © 2017, CC BY.