A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F08%3APU78081" target="_blank" >RIV/00216305:26230/08:PU78081 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata
Original language description
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.
Czech name
Uniformní (bi-)simulační framework pro redukci stromových automtů
Czech description
Práce popisuje uniformní framework pro kombinaci různých druhů simulací a bisimulací nad stromovými automaty s využitím pro redukci velikosti stromových automatů.
Classification
Type
D - Article in proceedings
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA102%2F07%2F0322" target="_blank" >GA102/07/0322: Advanced Formal Approaches in the Design and Verification of Computer-Based Systems</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
ISBN
978-80-7355-082-0
ISSN
—
e-ISSN
—
Number of pages
9
Pages from-to
—
Publisher name
Faculty of Informatics MU
Place of publication
Brno
Event location
Znojmo
Event date
Nov 14, 2008
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—