Publication Details

Composed Bisimulation for Tree Automata

ABDULLA Parosh A., BOUAJJANI Ahmed, HOLÍK Lukáš, KAATI Lisa and VOJNAR Tomáš. Composed Bisimulation for Tree Automata. In: Implementation and Application of Automata. Lecture Notes in Computer Science, vol. 5148. Berlin: Springer Verlag, 2008, pp. 212-222. ISBN 978-3-540-70843-8.
Czech title
Kombinovaná bisimulace pro stromové automaty
Type
conference paper
Language
english
Authors
Abdulla Parosh A. (Uppsala)
Bouajjani Ahmed (UPAR7)
Holík Lukáš, doc. Mgr., Ph.D. (DITS FIT BUT)
Kaati Lisa (Uppsala)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT)
Keywords

finite tree automata, bisimulation, size reduction

Abstract

We address the problem of reducing the size of (nondeterministic, bottom-up) tree automata using suitable, language-preserving equivalences on the states of the automata. In particular, we propose the so-called composed bisimulation as a new language preserving equivalence. Composed bisimulation is defined in terms of two different relations, namely upward and downward bisimulation. Moreover, we provide simple and efficient algorithms for computing composed bisimulation based on a reduction to the problem of computing bisimulations on (labeled) transition systems. The proposal of composed bisimulation is motivated by an attempt to obtain an equivalence that can provide better reductions than what currently known bisimulation-based approaches can offer, but which is not significantly more difficult to compute (and hence stays below the computational requirements of simulation-based reductions). The experimental results we present in the paper show that our composed bisimulation meets such requirements, and hence provides users of tree automata with a finer way to resolve the trade-off between the available degree of reduction and its cost.

Published
2008
Pages
212-222
Proceedings
Implementation and Application of Automata
Series
Lecture Notes in Computer Science
Volume
5148
Conference
13th International Conference on Implementation and Application of Automata -- CIAA'08, San Francisco, California, US
ISBN
978-3-540-70843-8
Publisher
Springer Verlag
Place
Berlin, DE
BibTeX
@INPROCEEDINGS{FITPUB8671,
   author = "A. Parosh Abdulla and Ahmed Bouajjani and Luk\'{a}\v{s} Hol\'{i}k and Lisa Kaati and Tom\'{a}\v{s} Vojnar",
   title = "Composed Bisimulation for Tree Automata",
   pages = "212--222",
   booktitle = "Implementation and Application of Automata",
   series = "Lecture Notes in Computer Science",
   volume = 5148,
   year = 2008,
   location = "Berlin, DE",
   publisher = "Springer Verlag",
   ISBN = "978-3-540-70843-8",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8671"
}
Back to top