Detail publikace

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

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

Originální název

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

Typ

zpráva odborná

Jazyk

angličtina

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 frameworkthat allows for combining various upward and downward bisimulation andsimulation relations in order to obtain a language-preserving combinedrelation suitable for reducing tree automata without a need todeterminise them. The framework gen- eralises and improves severalprevious works and provides a broad spectrum of different relationsyielding a possibility of a ?ne choice between the amount of re-duction and the computational demands. We analyse properties of theconsidered relations both theoretically as well as through a series ofexperiments.
 

Klíčová slova

tree automata, bisimulation, simulation, size reduction, framework

Autoři

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

Vydáno

12. 5. 2008

Místo

FIT-TR-2008-005, Brno

Strany počet

18

URL

http://www.fit.vutbr.cz/~holik/pub/FIT-TR-2008-005.pdf

BibTex

@techreport{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",
  year="2008",
  address="FIT-TR-2008-005, Brno",
  pages="18",
  url="http://www.fit.vutbr.cz/~holik/pub/FIT-TR-2008-005.pdf"
}