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

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 (170k 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
...