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 in constant 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.

Authors

• Andreas Maletti

Keywords

• Weighted tree automaton
• Minimization
• Tree series
• Determinism
• Partition refinement