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

Abstract : We propose a new approach for minimizing alternating Büchi 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üchi automata where ABA are used as an intermediate model.
Type de document :
Communication dans un congrès
Ravi Kannan and K Narayan Kumar. FSTTCS 2009 : IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2009, Kanpur, India. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, pp.1-12, 2009, 〈10.4230/LIPIcs.FSTTCS.2009.2302〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00459966
Contributeur : Brigitte Briot <>
Soumis le : jeudi 25 février 2010 - 16:45:22
Dernière modification le : jeudi 25 février 2010 - 17:23:32
Document(s) archivé(s) le : vendredi 18 juin 2010 - 21:55:47

Fichier

fsttcs09.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Parosh Za. Abdulla, Yu-Fang Chen, Lukas Holik, Tomas Vojnar. Mediating for Reduction (on Minimizing Alternating Büchi Automata). Ravi Kannan and K Narayan Kumar. FSTTCS 2009 : IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2009, Kanpur, India. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, pp.1-12, 2009, 〈10.4230/LIPIcs.FSTTCS.2009.2302〉. 〈inria-00459966〉

Partager

Métriques

Consultations de la notice

107

Téléchargements de fichiers

80