Technical report

ABDULLA, P., A., HOLÍK, L., CHEN, Y. and VOJNAR, T.. Mediating for Reduction (On Minimizing Alternating Büchi Automata). FIT-TR-2009-02, Brno, 2009.
Publication language:english
Original title:Mediating for Reduction (On Minimizing Alternating Büchi Automata)
Title (cs):Zprostředkování pro redukci (Za minimalizací alternujících automatů)
Pages:29
Place:FIT-TR-2009-02, Brno, CZ
Year:2009
URL:http://www.fit.vutbr.cz/~vojnar/Publications/achv-medForRed-tr-09.pdf [PDF]
Keywords
alternating automata, Büchi automata, reduction, simulation
Annotation
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.
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.
BibTeX:
@TECHREPORT{
   author = {A. Parosh Abdulla and Lukáš Holík and Yu-Fang Chen and Tomáš
	Vojnar},
   title = {Mediating for Reduction (On Minimizing Alternating Büchi
	Automata)},
   pages = {29},
   year = {2009},
   location = {FIT-TR-2009-02, Brno, CZ},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.en?id=9095}
}

Your IPv4 address: 50.17.174.94
Switch to IPv6 connection

DNSSEC [dnssec]