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

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

Paper in proceedings outside WoS and Scopus

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.

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.

tree automata, bisimulation, simulation, size reduction, framework

tree automata, bisimulation, simulation, size reduction, framework

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

2010

03.12.2008

Faculty of Informatics MU

Brno

978-80-7355-082-0

4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science

3

11

9