Minimizing deterministic weighted tree automata
Deterministic weighted tree automata (dwta) have found promising applications as language models in Natural Language Processing. It is known that dwta over commutative semifields can be effectively minimized. An efficient algorithm for minimizing them is presented. It is polynomial-time given that all operations of the semifield including the computation of the inverses are polynomial. More precisely, if the operations can be performed inconstant time, then the algorithm constructs an equivalent minimal(with respect to the number of states) dwta in time O(lmn) where l is the maximal rank of the input symbols, m is the number of (useful) transitions, and n is the number of states of the input dwta. (C) 2009 Elsevier Inc. All rights reserved.
minimization weighted tree automaton tree series determinism partition refinement