Publication result detail

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

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

Original Title

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

English Title

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

Type

Paper in proceedings outside WoS and Scopus

Original Abstract

Navrhli jsme novou metodu redukce alternujících Büchi automatůslučováním stavů ekvivalentních podle podle nové relace, takzvanezprostředkované (mediated) ekvivalenece. Zprostředkovaná ekvivalece jekombinací dopředné a zpětné simulace. Efektivitu metody jsme otestovalina experiementech s alternujícími automaty vznikajícími v rámcikomplementace Büchi automatů.

English abstract

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.

Key words in English

alternating automata, Büchi automata, reduction, simulation

Authors

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

RIV year

2010

Released

15.12.2009

Publisher

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Location

Wadern

ISBN

978-3-939897-13-2

Book

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

Edition

LIPIcs, sv. 4

Pages from

1

Pages to

12

Pages count

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="Mediating for Reduction (On Minimizing Alternating Büchi Automata)",
  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"
}