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ů
Pages:18
Place:FIT-TR-2008-005, Brno, CZ
Year:2008
URL:http://www.fit.vutbr.cz/~holik/pub/FIT-TR-2008-005.pdf [PDF]
Keywords
tree automata, bisimulation, simulation, size reduction, framework
Annotation
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.
 
BibTeX:
@TECHREPORT{
   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
	Automata},
   pages = {18},
   year = {2008},
   location = {FIT-TR-2008-005, Brno, CZ},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8620}
}

Your IPv4 address: 54.147.239.111
Switch to IPv6 connection

DNSSEC [dnssec]