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

557 users

0 votes
Hello

Please may explain Problem 6 in below exam?

https://es.cs.uni-kl.de/teaching/vrs/exams/2020.02.19.vrs/2020.02.19.vrs.solutions.pdf

Thanks.
in * TF "Intelligent Systems" by (770 points)

1 Answer

0 votes
Problem 6 has two parts: Part a) asks for translating a given LTL formula to an equivalent omega-automaton. There is a simple algorithm for this that you can find in the lecture slides. This algorithm makes use of a table that determines for each temporal logic operator the required transition relation and acceptance condition. These just have to be written down to obtain the omega-automaton listed in part a).

Part b) discusses whether two LTL formulas are equivalent based on a given path that consists of a cycle of three states s0->s1->s2->s0->... such that s0 is labeled with {b}, s1 is labeled with {a}, and s2 is labeled with {a,c}. You have to determine the truth values of the sub-formulas to finally see whether the given formulas are satisfied the same way on the given path or not. As shown in the solution, the formulas are evaluated differently, so that the path is a counterexample to the claim that the two formulas are equivalent. They are not equivalent as demonstrated with that path, and you should explain why that path tells us so.
by (170k points)
Thanks. I am referring part a. could you please mention slide no?
The core of the translation is listed on slide 73 for future operators and slide 74 for past operators. Slides 77-80 show by examples how the translation works. Slides following slide 82 show that sometimes, we may drop the acceptance conditions, if you want to improve the translation.

Related questions

0 votes
1 answer
asked Aug 27, 2021 in * TF "Intelligent Systems" by RS (770 points)
0 votes
1 answer
asked Aug 11, 2021 in * TF "Intelligent Systems" by RS (770 points)
+1 vote
2 answers
0 votes
1 answer
Imprint | Privacy Policy
...