Uniformní (bi-)simulační framework pro redukci stromových automtů

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

<a href="/cs/project/GA102%2F07%2F0322" target="_blank" >GA102/07/0322: Pokročilé formální přístupy v návrhu a automatické verifikaci počítačových systémů</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2008

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

ISBN

978-80-7355-082-0

ISSN

—

e-ISSN

—

Počet stran výsledku

9

Strana od-do

—

Název nakladatele

Faculty of Informatics MU

Místo vydání

Brno

Místo konání akce

Znojmo

Datum konání akce

14. 11. 2008

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—