Bisimulation Minimisation of Weighted Tree Automata
Andreas Maletti, Jonathan May · 2007
We generalise existing forward and backward bisimulation minimi- sation algorithms for tree automata to weighted tree automata. The obtained algorithms work for all semirings and retain the time complexity of their un- weighted variants for all additively cancellative semirings. On all other semirings the time complexity is slightly higher (linear instead of logarithmic in the num- ber of states of the input automaton). We demonstrate that weighted forward bisimulation minimisation can be used to minimise deterministic all-accepting weighted tree automata. Finally, we discuss implementations of these algorithms on a typical task in natural language processing. Copyright c 2007