A Uniform (Bi-)simulation-based Framework for Reducing Tree Automata

Abstract. In this paper, we address the problem of reducing the size of non-deterministic (bottom-up) tree automata. We propose a uniform framework that allows for combining various upward and downward bisimulation and simulation relations in order to obtain a language-preserving combined relation suitable for reducing tree automata without a need to determinise them. The framework gen-eralises and improves several previous works and provides a broad spectrum of different relations yielding a possibility of a fine choice between the amount of re-duction and the computational demands. We analyse properties of the considered relations both theoretically as well as through a series of experiments.