Publication detail

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

HOLÍK, L. VOJNAR, T. ABDULLA, P. KAATI, L.

Original Title

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

English Title

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

Type

journal article - other

Language

en

Original Abstract

In this paper, we address the problem of reducing the size of nondeterministic (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 generalises and extends several previous works and provides a broad spectrum of different relations yielding a possibility of a fine choice between the amount of reduction and the computational demands. We, moreover, provide a significantly improved way of computing the various combined (bi-)simulation relations. We analyse properties of the considered relations both theoretically as well as through a series of experiments.

English abstract

In this paper, we address the problem of reducing the size of nondeterministic (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 generalises and extends several previous works and provides a broad spectrum of different relations yielding a possibility of a fine choice between the amount of reduction and the computational demands. We, moreover, provide a significantly improved way of computing the various combined (bi-)simulation relations. We analyse properties of the considered relations both theoretically as well as through a series of experiments.

Keywords

tree automata, bisimulation, simulation, combined relations, size reduction

RIV year

2009

Released

03.09.2009

Publisher

NEUVEDEN

Location

NEUVEDEN

ISBN

1571-0661

Periodical

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE

Year of study

2009

Number

251

State

US

Pages from

27

Pages to

48

Pages count

22

URL

Documents

BibTex


@article{BUT49315,
  author="Lukáš {Holík} and Tomáš {Vojnar} and Parosh {Abdulla} and Lisa {Kaati}",
  title="A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata",
  annote="In this paper, we address the problem of reducing the size of nondeterministic
(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 generalises and
extends several previous works and provides a broad spectrum of different
relations yielding a possibility of a fine choice between the amount of reduction
and the computational demands. We, moreover, provide a significantly improved way
of computing the various combined (bi-)simulation relations. We analyse
properties of the considered relations both theoretically as well as through
a series of experiments.",
  address="NEUVEDEN",
  booktitle="Proceedings of the International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2008)",
  chapter="49315",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  journal="ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE",
  number="251",
  volume="2009",
  year="2009",
  month="september",
  pages="27--48",
  publisher="NEUVEDEN",
  type="journal article - other"
}