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

1.1k questions

1.2k answers


531 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 (166k points)
Imprint | Privacy Policy