Lectures 10 and 11: 5th November 2019 Flashcards Preview

CS4052 Logic and Software Verification > Lectures 10 and 11: 5th November 2019 > Flashcards

Flashcards in Lectures 10 and 11: 5th November 2019 Deck (74)
Loading flashcards...
1

What is a TS?

!

2

What is a PG?

!

3

What is an arbtier?

!

4

How can you implement mutual exclusion with an arbiter?

!

5

What is a semaphore?

!

6

How can you implement mutual exclusion with a semaphore?

!

7

How do you compose multiple PGs together?

!

8

How do you interleave multiple PGs together?

!

9

How do you find the reachable part of a TS?

!

10

When does a state satisfy a property?

!

11

When does a TS satisfy a property?

!

12

What is the difference between unconditional, strong, and weak fairness?

Unconditional = Every process gets its turn infinitely often.”

Strong = “Every process that is enabled infinitely often gets its turn infinitely often.”

Weak = “Every process that is continuously enabled from a certain time instant onwards gets its turn infinitely often.”

13

How can you formulate unconditional, strong, and weak fairness in LTL?

Unconditional = ufair = ☐◇criti

Strong = sfair = ☐◇waiti → ☐◇criti

Weak = wfair = ◇☐waiti → ☐◇criti

14

How can you formulate strong fairness in a TS of two composed PGs implementing mutual exclusion?

!

15

What is a linear logic?

!

16

What are the implications of LTL being a linear logic?

!

17

What types of formulae are easy, hard, and impossible to express in LTL?

!

18

What are branching logics?

!

19

What are branching time logics?

!

20

What are the unfoldings of a model?

!

21

What is CTL?

!

22

What are the two types of CTL formulae?

!

23

What are CTL state formulae?

!

24

What are CTL path formulae?

!

25

What is the format of CTL state formulae?

!

26

What is the format of CTL path formulae?

!

27

How can you convert between state and path formulae/

!

28

How must temporal operators be formatted to be legal in a state formula?

!

29

What do ∃ and ∀ mean in state formulae?

!

30

How do you formulate a mutual exclusion property in CTL?

!