Abstract

We generalise existing forward and backward bisimulation minimisation algorithms for tree automata to weighted tree automata. The obtained algorithms work for all semirings and retain the time complexity of their unweighted variants for all additively cancellative semirings. On all other semirings the time complexity is slightly higher (linear instead of logarithmic in the number of states). We discuss implementations of these algorithms on a typical task in natural language processing.

Date

2007

Authors

Johanna Högberg, Andreas Maletti, Jonathan May

Book

International Conference on Developments in Language Theory

Pages

229-241

Publisher

Springer Berlin Heidelberg