Bisimulation minimisation for weighted tree automata
2007 (English)In: Developments in Language Theory: 11th International Conference, DLT 2007, 2007Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
, Lecture Notes in Computer Science, ISSN 0302-9743
IdentifiersURN: urn:nbn:se:umu:diva-2417ISBN: 0302-9743OAI: oai:DiVA.org:umu-2417DiVA: diva2:140398