Technical report

ABDULLA Parosh A., HOLÍK Lukáš, KAATI Lisa and VOJNAR Tomáš. A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata. FIT-TR-2008-005, Brno, 2008.
Publication language:english
Original title:A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata
Title (cs):Uniformní (bi-)simulační framework pro redukci stromových automtů
Place:FIT-TR-2008-005, Brno, CZ
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.
   author = {A. Parosh Abdulla and Luk{\'{a}}{\v{s}} Hol{\'{i}}k and Lisa
	Kaati and Tom{\'{a}}{\v{s}} Vojnar},
   title = {A Uniform (Bi-)Simulation-Based Framework for Reducing Tree
   pages = {18},
   year = {2008},
   location = {FIT-TR-2008-005, Brno, CZ},
   language = {english},
   url = {}

Your IPv4 address:
Switch to IPv6 connection

DNSSEC [dnssec]