Conference paper

ABDULLA Parosh A., HOLÍK Lukáš, KAATI Lisa and VOJNAR Tomáš. A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata. In: 4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Faculty of Informatics MU, 2008, pp. 3-11. ISBN 978-80-7355-082-0.
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:3-11
Proceedings:4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Conference:MEMICS'08 -- 4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Place:Brno, CZ
Year:2008
ISBN:978-80-7355-082-0
Publisher:Faculty of Informatics MU
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:
@INPROCEEDINGS{
   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 = {3--11},
   booktitle = {4th Doctoral Workshop on Mathematical and Engineering
	Methods in Computer Science},
   year = {2008},
   location = {Brno, CZ},
   publisher = {Faculty of Informatics MU},
   ISBN = {978-80-7355-082-0},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8820}
}

Your IPv4 address: 54.224.121.67
Switch to IPv6 connection

DNSSEC [dnssec]