Publication Details

A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata

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.
Czech title
Uniformní (bi-)simulační framework pro redukci stromových automtů
Type
conference paper
Language
english
Authors
Abdulla Parosh A. (Uppsala)
Holík Lukáš, doc. Mgr., Ph.D. (DITS FIT BUT)
Kaati Lisa (Uppsala)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT)
Keywords

tree automata, bisimulation, simulation, size reduction, framework

Abstract

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.

Published
2008
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, Znojmo, CZ
ISBN
978-80-7355-082-0
Publisher
Faculty of Informatics MU
Place
Brno, CZ
BibTeX
@INPROCEEDINGS{FITPUB8820,
   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 = "https://www.fit.vut.cz/research/publication/8820"
}
Back to top