Detail publikace

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

HOLÍK, L. VOJNAR, T. ABDULLA, P. CHEN, Y.

Originální název

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

Anglický název

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

Typ

článek ve sborníku mimo WoS a Scopus

Jazyk

čeština

Originální abstrakt

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

Anglický abstrakt

We propose a new approach for minimizing alternating Büchi automata (ABA). The approach is based on the so called mediated equivalence on states of ABA, which is the maximal equivalence contained in the so called mediated preorder. Two states p and q can be related by the mediated preorder if there is a mediator (mediating state) which forward simulates p and backward simulates q. Under some further conditions, letting a computation on some word jump from q to p (due to they get collapsed) 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 more significant reductions when applied within the process of complementing Büchi automata where ABA are used as an intermediate model.

Klíčová slova v angličtině

alternating automata, Büchi automata, reduction, simulation

Autoři

HOLÍK, L.; VOJNAR, T.; ABDULLA, P.; CHEN, Y.

Rok RIV

2009

Vydáno

15. 12. 2009

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo

Wadern

ISBN

978-3-939897-13-2

Kniha

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

Edice

LIPIcs, sv. 4

Strany od

1

Strany do

12

Strany počet

12

URL

http://www.fit.vutbr.cz/~holik/pub/FSTTCS09.pdf

BibTex

@inproceedings{BUT30903,
  author="Lukáš {Holík} and Tomáš {Vojnar} and Parosh {Abdulla} and Yu-Fang {Chen}",
  title="Zprostředkování pro redukci (Za minimalizací alternujících automatů)",
  booktitle="IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)",
  year="2009",
  series="LIPIcs, sv. 4",
  pages="1--12",
  publisher="Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",
  address="Wadern",
  isbn="978-3-939897-13-2",
  url="http://www.fit.vutbr.cz/~holik/pub/FSTTCS09.pdf"
}