A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata

In this paper, we address the problem of reducing the size of non-deterministic (bottom-up) tree automata. We propose a uniform frameworkthat allows for combining various upward and downward bisimulation andsimulation relations in order to obtain a language-preserving combinedrelation suitable for reducing tree automata without a need todeterminise them. The framework gen- eralises and improves severalprevious works and provides a broad spectrum of different relationsyielding a possibility of a ?ne choice between the amount of re-duction and the computational demands. We analyse properties of theconsidered relations both theoretically as well as through a series ofexperiments.