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
@inproceedings{BUT33442,
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.",
address="Faculty of Informatics MU",
booktitle="4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science",
chapter="33442",
edition="NEUVEDEN",
howpublished="print",
institution="Faculty of Informatics MU",
year="2008",
month="december",
pages="3--11",
publisher="Faculty of Informatics MU",
type="conference paper"
}