License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2302
URN: urn:nbn:de:0030-drops-23027
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2302/
Abdulla, Parosh A. ;
Chen, Yu-Fang ;
Holik, Lukas ;
Vojnar, Tomas
Mediating for Reduction (on Minimizing Alternating Büchi Automata)
Abstract
We propose a new approach for minimizing alternating B\"uchi automata (ABA). The approach is based on the so called \emph{mediated equivalence} on states of ABA, which is the maximal equivalence contained in the so called \emph{mediated preorder}. Two states $p$ and $q$ can be related by the mediated preorder if there is a~\emph{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\"uchi automata where ABA are used as an intermediate model.
BibTeX - Entry
@InProceedings{abdulla_et_al:LIPIcs:2009:2302,
author = {Parosh A. Abdulla and Yu-Fang Chen and Lukas Holik and Tomas Vojnar},
title = {{Mediating for Reduction (on Minimizing Alternating B{\"u}chi Automata)}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {1--12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-13-2},
ISSN = {1868-8969},
year = {2009},
volume = {4},
editor = {Ravi Kannan and K. Narayan Kumar},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2302},
URN = {urn:nbn:de:0030-drops-23027},
doi = {10.4230/LIPIcs.FSTTCS.2009.2302},
annote = {Keywords: Alternating Automata, Buchi Automata, Automata Minimization, Buchi Automata Complementation, Simulation Preorder, forward and backward simulation,}
}
|
Keywords: |
|
Alternating Automata, Buchi Automata, Automata Minimization, Buchi Automata Complementation, Simulation Preorder, forward and backward simulation, |
|
Freie Schlagwörter (englisch): |
|
mediated equivalence |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
|
Issue Date: |
|
2009 |
|
Date of publication: |
|
07.12.2009 |
