Publication Details
A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata
Vojnar Tomáš, prof. Ing., Ph.D. (DITS)
Abdulla Parosh
Kaati Lisa
tree automata, bisimulation, simulation, size reduction, framework
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 ?ne 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.
@techreport{BUT63768,
author="Lukáš {Holík} and Tomáš {Vojnar} and Parosh {Abdulla} and Lisa {Kaati}",
title="A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata",
year="2008",
address="FIT-TR-2008-005, Brno",
pages="18",
url="http://www.fit.vutbr.cz/~holik/pub/FIT-TR-2008-005.pdf"
}