Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.3k answers

1.7k comments

556 users

0 votes



In the above question, non-deterministic safety automata is not totally defined, so why are we using subset construction instead of breakpoint construction for determinizing? 

For totally defined automata, we use rabin-scott and for partially defined we use breakpoint construction right?

in TUK (TU Kaiserslautern) by (380 points)

1 Answer

0 votes
For safety automata, we can use the subset construction regardless whether the safety automaton is totally defined or not. We even have to remove the unsafe states which removes further transitions of the automaton. After this, we apply the subset construction.

The issue you have in mind is only for liveness automata that can be determinized with the subset construction if they are totally defined, and otherwise, we have to use the breakpoint construction after transforming the liveness automaton to a co-Büchi automaton.
by (170k points)
Imprint | Privacy Policy
...