Publication detail
Composed Bisimulation for Tree Automata
HOLÍK, L. VOJNAR, T. ABDULLA, P. BOUAJJANI, A. KAATI, L.
Original Title
Composed Bisimulation for Tree Automata
English Title
Composed Bisimulation for Tree Automata
Type
conference paper
Language
en
Original 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.
English 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.
Keywords
finite tree automata, bisimulation, size reduction
RIV year
2008
Released
18.08.2008
Publisher
Springer Verlag
Location
Berlin
ISBN
978-3-540-70843-8
Book
Implementation and Application of Automata
Edition
Lecture Notes in Computer Science
Edition number
NEUVEDEN
Pages from
212
Pages to
222
Pages count
11
Documents
BibTex
@inproceedings{BUT34274,
author="Lukáš {Holík} and Tomáš {Vojnar} and Parosh {Abdulla} and Ahmed {Bouajjani} and Lisa {Kaati}",
title="Composed Bisimulation for Tree Automata",
annote="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.",
address="Springer Verlag",
booktitle="Implementation and Application of Automata",
chapter="34274",
edition="Lecture Notes in Computer Science",
howpublished="print",
institution="Springer Verlag",
journal="Lecture Notes in Computer Science (IF 0,513)",
year="2008",
month="august",
pages="212--222",
publisher="Springer Verlag",
type="conference paper"
}