Detail publikace

Composed Bisimulation for Tree Automata

Originální název

Composed Bisimulation for Tree Automata

Anglický název

Composed Bisimulation for Tree Automata

Jazyk

en

Originální abstrakt

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.

Anglický abstrakt

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.

BibTex


@misc{BUT63382,
  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.",
  chapter="63382",
  year="2008",
  month="may",
  type="presentation"
}