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 and technology
- 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: 85
File downloads:
- IWP15_01_diuf.pdf: 142