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 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.
@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"
}