Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

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

Lectures 10 and 11: 5th November 2019 Flashcards

LTL fairness, CTL, async comms, timed automata

1
Q

What is a TS?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a PG?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is an arbtier?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

How can you implement mutual exclusion with an arbiter?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a semaphore?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

How can you implement mutual exclusion with a semaphore?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

How do you compose multiple PGs together?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How do you interleave multiple PGs together?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How do you find the reachable part of a TS?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

When does a state satisfy a property?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

When does a TS satisfy a property?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

Unconditional = ufair = ☐◇criti

Strong = sfair = ☐◇waiti → ☐◇criti

Weak = wfair = ◇☐waiti → ☐◇criti

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a linear logic?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the implications of LTL being a linear logic?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are branching logics?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are branching time logics?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What are the unfoldings of a model?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is CTL?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What are the two types of CTL formulae?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What are CTL state formulae?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What are CTL path formulae?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is the format of CTL state formulae?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is the format of CTL path formulae?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

How can you convert between state and path formulae/

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

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

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What do ∃ and ∀ mean in state formulae?

A

!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

How do you formulate a mutual exclusion property in CTL?

A

!

31
Q

What are the equivalence laws of CTL?

A

!

32
Q

When does a state satisfy a CTL state formula?

A

!

33
Q

When does a path satisfy a CTL path formula?

A

!

34
Q

What is the satisfaction set of a CTL state formula?

A

!

35
Q

When are two CTL formulae equivalent?

A

!

36
Q

Give the basic model checking algorithm for CTL formulae.

A

!

37
Q

What are synchronous and asynchronous communications?

A

!

38
Q

What are channel systems?

A

!

39
Q

How do channel systems work in PROMELA?

A

!

40
Q

What are communication actions in PROMELA?

A

!

41
Q

How are communiation actions formatted in PROMELA?

A

!

42
Q

What is the capacity of a channel?

A

!

43
Q

How does handshaking work in PROMELA?

A

!

44
Q

How do you find the capacity of a channel in PROMELA?

A

!

45
Q

When can processes send and get messages into or from a channel?

A

!

46
Q

What are channel systems?

A

!

47
Q

What are channel systems used for in PROMELA?

A

!

48
Q

What is alternating bit protocol?

A

!

49
Q

How does ABP implement reliable comms over unreliable channels?

A

!

50
Q

How does ABP work?

A

!

51
Q

What are concurrent systems?

A

!

52
Q

What are the differences between different concurrent systems?

A

!

53
Q

What are timed automata?

A

!

54
Q

How do timed automata work?

A

!

55
Q

What is UPPAAL?

A

!

56
Q

How does UPPAAL work?

A

!

57
Q

What is TCTL?

A

!

58
Q

How does TCTL work?

A

!

59
Q

What are untimed models?

A

!

60
Q

What are untimed actions?

A

!

61
Q

How do untimed models work?

A

!

62
Q

What are real-time constraints?

A

!

63
Q

How can you implement timed models with and without using timed automata?

A

!

64
Q

Is it easier to implement timed models with or without timed automata? Why?

A

!

65
Q

Why is using a set of clocks acting as stopwatches a poor solution for implementing timed automata?

A

!

66
Q

How do timed automata work, in detail?

A

!

67
Q

What are clock constraints?

A

!

68
Q

How do you mathematically define a timed automaton?

A

!

69
Q

How are transitions in timed automata formatted?

A

!

70
Q

What are location invariants in timed automata?

A

!

71
Q

How do you implement location invariants in timed automata?

A

!

72
Q

What is the difference between guards and location invariants in timed automata?

A

!

73
Q

How do clocks work in timed automata?

A

!

74
Q

How are clocks implemented in timed automata?

A

!

CS4052 Logic and Software Verification (17 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions