Journal article

ABDULLA, P., A., HOLÍK, L., KAATI, L. and VOJNAR, T.. A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. 2009, vol. 2009, no. 251, pp. 27-48. ISSN 1571-0661.
Publication language:english
Original title:A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata
Title (cs):Uniformní systém (bi)simulačních relací pro redukci stromových automatů
Pages:27-48
Book:Proceedings of the International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2008)
Place:US
Year:2009
Journal:ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, Vol. 2009, No. 251, US
ISSN:1571-0661
URL:http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B75H1-4X4H7HH-4-1&_cdi=13109&_user=10&_orig=browse&_coverDate=09%2F03%2F2009&_sk=997489999&view=c&wchp=dGLzVzz-zSkWb&md5=3c75609f2ce3e4e6b25134896766eee6&ie=/sdarticle.pdf [PDF]
Keywords
tree automata, bisimulation, simulation, combined relations, size reduction
Annotation
In this paper, we address the problem of reducing the size of nondeterministic (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 generalises and extends several previous works and provides a broad spectrum of different relations yielding a possibility of a fine choice between the amount of reduction and the computational demands. We, moreover, provide a significantly improved way of computing the various combined (bi-)simulation relations. We analyse properties of the considered relations both theoretically as well as through a series of experiments.
BibTeX:
@ARTICLE{
   author = {A. Parosh Abdulla and Lukáš Holík and Lisa Kaati and Tomáš
	Vojnar},
   title = {A Uniform (Bi-)Simulation-Based Framework for Reducing Tree
	Automata},
   pages = {27--48},
   booktitle = {Proceedings of the International Doctoral Workshop on
	Mathematical and Engineering Methods in Computer Science
	(MEMICS 2008)},
   journal = {ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE},
   volume = {2009},
   number = {251},
   year = {2009},
   ISSN = {1571-0661},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.en?id=9030}
}

Your IPv4 address: 50.17.86.12
Switch to IPv6 connection

DNSSEC [dnssec]