Mediating for Reduction (on Minimizing Alternating Büchi Automata) - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

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

Résumé

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.
Fichier principal
Vignette du fichier
fsttcs09.pdf (494.82 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

inria-00459966 , version 1 (25-02-2010)

Identifiants

Citer

Parosh Za. Abdulla, Yu-Fang Chen, Lukas Holik, Tomas Vojnar. Mediating for Reduction (on Minimizing Alternating Büchi Automata). FSTTCS 2009 : IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2009, Kanpur, India. pp.1-12, ⟨10.4230/LIPIcs.FSTTCS.2009.2302⟩. ⟨inria-00459966⟩

Collections

CONNECT
86 Consultations
211 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More