Title: Bisimulation Minimisation of Weighted Tree Automata
Abstract: 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
Publication Year: 2007
Publication Date: 2007-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 4
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot