Mediating for reduction (on minimizing alternating Buchi automata)

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F14%3APU112069" target="_blank" >RIV/00216305:26230/14:PU112069 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.tcs.2014.08.003" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2014.08.003</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2014.08.003" target="_blank" >10.1016/j.tcs.2014.08.003</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Mediating for reduction (on minimizing alternating Buchi automata)

Popis výsledku v původním jazyce

We propose a new approach for minimizing alternating Buchi automata (ABA). The approach is based on the mediated equivalence on states of an ABA, which is the maximal equivalence contained in the mediated preorder. Two states p and q are related by the mediated preorder if there is a~mediator (mediating state) which forward simulates p and backward simulates q. Under further conditions, letting a computation on some word jump from q to p preserves the language as the automaton can anyway already accept the word without jumps by runs through the mediator. We further show how the mediated equivalence can be computed efficiently. Finally, we show that, compared to the standard forward simulation equivalence, the mediated equivalence can yield much larger reductions when applied within the process of complementing Buchi automata where ABA are used as an intermediate model.

Název v anglickém jazyce

Mediating for reduction (on minimizing alternating Buchi automata)

Popis výsledku anglicky

We propose a new approach for minimizing alternating Buchi automata (ABA). The approach is based on the mediated equivalence on states of an ABA, which is the maximal equivalence contained in the mediated preorder. Two states p and q are related by the mediated preorder if there is a~mediator (mediating state) which forward simulates p and backward simulates q. Under further conditions, letting a computation on some word jump from q to p preserves the language as the automaton can anyway already accept the word without jumps by runs through the mediator. We further show how the mediated equivalence can be computed efficiently. Finally, we show that, compared to the standard forward simulation equivalence, the mediated equivalence can yield much larger reductions when applied within the process of complementing Buchi automata where ABA are used as an intermediate model.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2014

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 periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

1879-2294

Svazek periodika

2014

Číslo periodika v rámci svazku

552

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

18

Strana od-do

26-43

Kód UT WoS článku

000342475400003

EID výsledku v databázi Scopus

2-s2.0-84926326209