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

1.6k comments

524 users

0 votes

Hi, 

I have doubts regarding omega automaton 

In these two question, i got the transition diagram properly. But I don't understand why we used subset construction here? 

In the first part (7 (a))  it's mentioned that we have to deterministic safety automaton, so we can use subset contruction. 

But what about (7(b)). How we can use subset construction there?

in # Study-Organisation (Master) by (2.7k points)

1 Answer

+1 vote
 
Best answer
Temporal logic formulas can often be better understood when these are translated to deterministic automata. F[a SU b] cannot be translated to Det-G but to Det-F. However, if you use the standard translation, you will get two GF-constraints, However, determinizing B├╝chi automata is very difficult.

Hence, we use the following workaround: We translate !F[a SU b] to a NDet-G automaton, determinize it to a Det-G automaton, and negate it to get a Det-F automaton equivalent to F[a SU b].
by (165k points)
selected by
Thanks for the explanation. I understood.

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
Imprint | Privacy Policy
...