Internal working papers DIUF

Internal working papers DIUF
La collection des Internal working papers DIUF est une série de rapports de recherche édités par le Département d'Informatique de l'Université de Fribourg (Suisse). Cette collection existe depuis 1958 et elle est intégralement disponible sous forme électronique depuis 2015. Les contenus des publications s'inscrivent dans les thématiques de recherche de l’informatique, de la recherche opérationnelle et des statistiques.
La collection a été publiée sous le nom de l’Institut d’Automation (IAUF), de 1958 à 1995, et du Laboratoire d’Informatique (LIUF), de 1986 à 1995, puis sous le nom de l’Institut d’Informatique (IIUF), de 1995 à 2000.

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...