Minimal separating sets for acceptance conditions in Muller Automata
✍ Scribed by Helmut Lescow; Jens Vöge
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 115 KB
- Volume
- 231
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
For a Muller automaton only a subset of its states is needed to decide whether a run is accepting or not. The set I of the inÿnitely often visited states can be replaced by the intersection I ∩ W with a ÿxed set W of states, provided W is large enough to distinguish between accepting and non-accepting loops in the automaton. We call such a subset W a separating set. Whereas the idea was previously introduced by McNaughton (Ann. Pure Appl. Logic 65 (1993) 149 -184), the algorithmic construction of the smallest separating sets is not treated in the literature. In this paper we show that the problem whether in a Muller automaton a separating set of a given size exists is NP-complete. As a step towards an e cient computation of a separating set of minimal size we present an algorithm in the second part of the paper, based on an analysis of the loop structure of the given automaton.