Research report

Complementing Büchi automata with a subset-tuple construction

    01.03.2015

16

English 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 tuples of subsets of states) that produces a deterministic automaton. This construction leads to a complementation procedure that resembles the straightforward complementation algorithm for deterministic Büchi automata, the latter algorithm actually being a special case of our construction.
Collections
Faculty
Faculté des sciences et de médecine
Department
Département d'informatique
Language
  • English
Classification
Computer science
Series statement
  • Internal working papers DIUF ; 15-01
License
License undefined
Identifiers
  • RERO DOC 260772
  • RERO R008436997
Persistent URL
https://folia.unifr.ch/unifr/documents/304914
Statistics

Document views: 13 File downloads:
  • IWP15_01_diuf.pdf: 2