Zprostředkování pro redukci (Za minimalizací alternujících automatů)

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F09%3APU86210" target="_blank" >RIV/00216305:26230/09:PU86210 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

čeština

Název v původním jazyce

Zprostředkování pro redukci (Za minimalizací alternujících automatů)

Popis výsledku v původním jazyce

Navrhli jsme novou metodu redukce alternujících Büchi automatů slučováním stavů ekvivalentních podle podle nové relace, takzvane zprostředkované (mediated) ekvivalenece. Zprostředkovaná ekvivalece je kombinací dopředné a zpětné simulace. Efektivitu metody jsme otestovali na experiementech s alternujícími automaty vznikajícími v rámci komplementace Büchi automatů.<br>

Název v anglickém jazyce

Mediating for Reduction (On Minimizing Alternating Büchi Automata)

Popis výsledku anglicky

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

Druh

D - Stať ve sborníku

CEP obor

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

OECD FORD obor

—

Projekt

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

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2009

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

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

ISBN

978-3-939897-13-2

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

—

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo vydání

Wadern

Místo konání akce

Kanpur

Datum konání akce

14. 12. 2009

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

WRD - Celosvětová akce

Kód UT WoS článku

—