Affiner les résultats

Type de document

  • Rapports de recherche désactiver le filtre

Institution

Collection spécifique

Langue

Auteur

Mot clé

    Université de Fribourg

    Complementing Büchi automata with a subset-tuple construction

    Allred, Joel ; Ultes-Nitsche, Ulrich

    (Internal working papers DIUF ; 15-01)

    Complementation of Büchi automata is well known for being difficult. In the worst case, a state-space growth of (0:76n)n is unavoidable. Recent studies suggest that “simpler” algorithms perform better than more involved ones on practical cases. In this paper, we present a simple “direct” algorithm for complementing Büchi automata. It involves a structured subset construction (using...