Internal working papers DIUF

Internal working papers DIUF
The DIUF Working Papers collection is a series of research papers edited by the Department of Informatics of the University of Fribourg (Switzerland). This series exists since 1958, and is available in its entirety in electronic form since 2015. The content of the publications fits into the research themes of informatics, operational research and statistics.
The collection has been published under the names of the Institute of Automation (IAUF) from 1958 to 1995, the Laboratory of Informatics (LIUF) from 1986 to 1995, and the Institute of Informatics (IIUF) from 1995 to 2000.

Refine my results





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