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

journal article - other

Language

en

Original Abstract

We address the problem of reducing the size of (nondeterministic, bottom-up) tree automata (TA) using suitable, language-preserving equivalences on the states of the automata. In particular, we propose the so-called composed bisimulation equivalence as a new language preserving equivalence. A composed bisimulation equivalence is defined in terms of two different relations, namely the upward and downward bisimulation equivalence. We provide simple and efficient algorithms for computing these relations. The notion of composed bisimulation equivalence 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 equivalence meets such requirements, and hence provides users of TA 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 (TA) using suitable, language-preserving equivalences on the states of the automata. In particular, we propose the so-called composed bisimulation equivalence as a new language preserving equivalence. A composed bisimulation equivalence is defined in terms of two different relations, namely the upward and downward bisimulation equivalence. We provide simple and efficient algorithms for computing these relations. The notion of composed bisimulation equivalence 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 equivalence meets such requirements, and hence provides users of TA 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

2009

Released

01.08.2009

Publisher

NEUVEDEN

Location

NEUVEDEN

ISBN

0129-0541

Periodical

International Journal of Foundations of Computer Science

Year of study

20

Number

4

State

SG

Pages from

685

Pages to

700

Pages count

16

URL

Documents

BibTex


@article{BUT47978,
  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 (TA) using suitable, language-preserving equivalences on the states of
the automata. In particular, we propose the so-called composed bisimulation
equivalence as a new language preserving equivalence. A composed bisimulation
equivalence is defined in terms of two different relations, namely the upward and
downward bisimulation equivalence. We provide simple and efficient algorithms for
computing these relations. The notion of composed bisimulation equivalence 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 equivalence
meets such requirements, and hence provides users of TA with a finer way to
resolve the trade-off between the available degree of reduction and its cost.",
  address="NEUVEDEN",
  chapter="47978",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  journal="International Journal of Foundations of Computer Science",
  number="4",
  volume="20",
  year="2009",
  month="august",
  pages="685--700",
  publisher="NEUVEDEN",
  type="journal article - other"
}