Conference paperABDULLA Parosh A., HOLÍK Lukáš, CHEN YuFang and VOJNAR Tomáš. Mediating for Reduction (On Minimizing Alternating Büchi Automata). In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009). Wadern: Schloss DagstuhlLeibnizZentrum fuer Informatik, 2009, pp. 112. ISBN 9783939897132.  Publication language:  czech 

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

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

Pages:  112 

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

Conference:  Annual Conference on Foundations of Software Technology and Theoretical Computer Science 

Series:  LIPIcs, sv. 4 

Place:  Wadern, DE 

Year:  2009 

ISBN:  9783939897132 

Publisher:  Schloss DagstuhlLeibnizZentrum fuer Informatik 

URL:  http://www.fit.vutbr.cz/~holik/pub/FSTTCS09.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: 

@INPROCEEDINGS{
author = {A. Parosh Abdulla and Luk{\'{a}}{\v{s}} Hol{\'{i}}k and
YuFang Chen and Tom{\'{a}}{\v{s}} Vojnar},
title = {Mediating for Reduction (On Minimizing Alternating
B{\"{u}}chi Automata)},
pages = {112},
booktitle = {IARCS Annual Conference on Foundations of Software
Technology and Theoretical Computer Science (2009)},
series = {LIPIcs, sv. 4},
year = {2009},
location = {Wadern, DE},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
ISBN = {9783939897132},
language = {czech},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9140}
} 
