Internal working papers DIUF

Internal working papers DIUF
Die Sammlung der Working Papers des DIUF ist eine Serie von Forschungsberichten, die das Departement für Informatik der Universität Freiburg (Schweiz) veröffentlicht hat. Diese Sammlung existiert seit 1958 und ist seit 2015 vollständig in digitaler Form verfügbar. Die Inhalte der Publikationen behandeln Themen der Forschung im Bereich Informatik, Operations Research und der Statistiken.
Die Sammlung wurde publiziert in den Jahren 1958 bis 1995 unter dem Namen Institut für Automation (IAUF) und in den Jahren 1986 bis 1995 unter dem Namen Laboratorium für Informatik (LIUF) veröffentlicht, später von 1995 bis 2000 unter dem Namen Institut für Informatik (IIUF).
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...