10.4230/LIPICS.FSTTCS.2009.2302
Abdulla, Parosh A.
Parosh A.
Abdulla
Chen, Yu-Fang
Yu-Fang
Chen
Holik, Lukas
Lukas
Holik
Vojnar, Tomas
Tomas
Vojnar
Mediating for Reduction (on Minimizing Alternating Büchi Automata)
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2009
Alternating Automata
Buchi Automata
Automata Minimization
Buchi Automata Complementation
Simulation Preorder
forward and backward simulation
mediated equivalence
Kannan, Ravi
Ravi
Kannan
Kumar, K. Narayan
K. Narayan
Kumar
2009
2009-12-07
2009-12-07
2009-12-07
en
urn:nbn:de:0030-drops-23027
10.4230/LIPIcs.FSTTCS.2009
978-3-939897-13-2
1868-8969
10.4230/LIPIcs.FSTTCS.2009
LIPIcs, Volume 4, FSTTCS 2009
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
4
1
1
12
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Kannan, Ravi
Ravi
Kannan
Kumar, K. Narayan
K. Narayan
Kumar
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2009
4
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
738872 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 1-12