Backward and forward bisimulation minimisation of tree automata
2007 (English)In: Implementation and Application of Automata: 12th International Conference, CIAA 2007, 2007Conference paper (Refereed)
We improve an existing bisimulation minimisation algorithm for tree automata by introducing backward and forward bisimulations and developing minimisation algorithms for them. Minimisation via forward bisimulation is effective for deterministic automata and faster than the previous algorithm. Minimisation via backward bisimulation generalises the previous algorithm and is thus more effective but just as fast. We demonstrate 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-2416OAI: oai:DiVA.org:umu-2416DiVA: diva2:140397