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

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F08%3APU80184" target="_blank" >RIV/00216305:26230/08:PU80184 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

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.<br>&nbsp;

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ů.<br>

Type

A - Audiovisual production

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2008

Confidentiality

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

ISBN

—

Place of publication

—

Publisher/client name

—

Version

—

Carrier ID

—