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