Detail publikace

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

Originální název

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

Anglický název

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

Jazyk

en

Originální abstrakt

In this paper, we address the problem of reducing the size of non- deterministic (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 gen- eralises and improves several previous works and provides a broad spectrum of different relations yielding a possibility of a ?ne choice between the amount of re- duction and the computational demands. We analyse properties of the considered relations both theoretically as well as through a series of experiments.
 

Anglický abstrakt

In this paper, we address the problem of reducing the size of non- deterministic (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 gen- eralises and improves several previous works and provides a broad spectrum of different relations yielding a possibility of a ?ne choice between the amount of re- duction and the computational demands. We analyse properties of the considered relations both theoretically as well as through a series of experiments.
 

BibTex


@misc{BUT63768,
  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 non-
deterministic (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 gen- eralises and improves several
previous works and provides a broad spectrum of different relations
yielding a possibility of a ?ne choice between the amount of re-
duction and the computational demands. We analyse properties of the
considered relations both theoretically as well as through a series of
experiments.
 ", chapter="63768", year="2008", month="may", type="presentation" }