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


510 users

0 votes

1) For Non-Deterministic liveness automat, when to use subset and when to use breakpoint construction.

As per my understanding, non-deterministic partial liveness automata shall be converted into prefix non-deterministic liveness automata and then use subset construction to determinize, right?

But in slides it is also mentioned that non-deterministic liveness automata will go to non-deterministic co-buchi and then finally into deterministic co-buchi using breakpoint. so in this case, what  shall be used to convert non-deterministic liveness to non-deterministic co-buchi?

I am confused for liveness automat when to use what?

Please explain

in * TF "Emb. Sys. and Rob." by (440 points)

1 Answer

0 votes

Simply proceed as follows:

  • If a nondeterministic liveness automaton is totally defined, use the subset construction. That will always work.
  • If missing transitions of a partially defined nondeterministic liveness automaton can be added to make it totally defined without changing its accepted language (which is in general not easy to see, but often, it is!), then use the subset construction for the totally defined automaton.
  • Otherwise, i.e., if. the partially defined automaton cannot be made total, convert it to an equivalent co-B├╝chi automaton and use the breakpoint construction.

The third case is unavoidable in some cases, since nondeterministic liveness automata are in general more powerful than the deterministic liveness automata.

by (162k points)
Imprint | Privacy Policy