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 > Exam: Question 4 > Flashcards

Exam: Question 4 Flashcards

TSes, Petri nets, and LTL

1
Q

What is a petri net?

A

A mathematical model of distributed systems made of tokens, places, and transitions, which can allow concurrency.

Places are similar to locations and are represented by circles.

Tokens are objects/resources, represented by dots inside locations.

Transitions are modelled as squares/rectangles and move tokens between locations.

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

How do you give petri nets that generate all words that are prefixes of a given language?

A

!

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

How do you make a petri net to model an example of mutual exclusion with 2 processes?

A

Have two competing processes and a mutex place. Both transitions to allow both access to their critical sections require both the mutex and waiting place for the process to have a token, and removes them from both, placing a token into the processes’ critical section place. Then once done, the token is removed and the tokens in the waiting place and mutex place are restored.

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

How can you show a Petri net model satisfies mutual exclusion?

A

!

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

What are partial semantics?

A

!

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

How do you find the partial semantics for all given programs and states?

A

!

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

What is a correctness condition?

A

!

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

What is the syntax of correctness conditions?

A

!

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

How do you prove or disprove correctness conditions against a given program?

A

!

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

How do you form correctness conditions to describe the behavior of programs?

A

!

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

How do you perform a parallel composition of 2 TSes?

A
  • draw the TSes out individually with their states, transitions, and APs
  • find all possible unique pairs of states
  • draw the transitions between the states based upon the changes that cause them in the original TSes
  • eliminate unreachable states
  • eliminate states where only 1 state changes but both would for the same action
  • add APs to each state pair by appending those in states in each individual TS
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How do you perform handshaking composition on two TSes?

A

!

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

How do you give the minimal petri net equivalent to a TS?

A

!

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

How do you find which parts of a petri net are equivalent to a TS which the petri net is equivalent to?

A

!

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

What are the differences between TSes and petri nets?

A

!

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

How can you find a safety property that holds in one composed TS but not another?

A

!

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

How do you define the satisfaction of LTL formulae [] p and <> p over Petri nets, where p is an atomic proposition? Illustrate your answer.

A

!

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

How do you make a petri net that produces a given language?

A

!

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

How do you find the reachable states in a pseudocode program with processes from a given start state and variable value?

A

!

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

How do you make a correctness condition to describe the behavior of a program with respect to a variable?

A

!

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

How do you find the reachability graph of a petri net?

A

!

22
Q

How do you find the overlapping graph of a petri net?

A

!

23
Q

How do you model a real-world system with a petri net?

A

!

24
Q

How do you find which states are reachable from a given start state with given starting variable values for a program running given processes?

A

!

25
Q

How do you show whether a TS holds a given LTL formula with a given fairness constraint?

A

!

26
Q

How do you find a path for which a TS does not hold a given LTL formula?

A

!

27
Q

How do you model a given algorithm with petri nets?

A

!

28
Q

How can you show whether a petri net satisfies starvation freedom?

A

!

29
Q

How do you define the semantics of LTL for petri nets to describe properties of state-based semantics?

A

!

30
Q

How can you find a valid global execution fragment of a given TS?

A

!

31
Q

How can you find an invalid global execution fragment of a given TS?

A

!

32
Q

How can you find a valid global execution fragment of a given composed TS?

A

!

33
Q

How can you find an invalid global execution fragment of a given composed TS?

A

!

34
Q

How do you interleaved TSes?

A

!

35
Q

What is the difference between parallel composition and interleaving? How are the two notated? What can you perform them on?

A

!

36
Q

How do you find a petri net equivalent to a TS with synchronisation constraints?

A

!

37
Q

What are synchronisation constraints?

A

!

38
Q

How do synchronisation constraints work?

A

!

39
Q

Give an inductive definition of LTL over a nonempty set of atomic propositions, AP.

A

!

40
Q

What do [] ( p ⇒ X ¬ p ) and <> ( p ∧ X p ) assert? How are they related?

A

!

41
Q

How are products of transition systems model checked against LTL formulae?

A

!

42
Q

What difference would it make to consider the product of TSes against LTL formulae into petri nets?

A

!

43
Q

How can you find a valid execution fragment of a given TS?

A

!

44
Q

How can you find an invalid execution fragment of a given TS?

A

!

45
Q

How can you convert a formally defined TS into a pictoral representation?

A

!

46
Q

How can you convert a pictoral TS into a petri net?

A

!

47
Q

How do you define the semantics for a new concurrency operator over petri nets?

A

!

48
Q

Why is it possible to define concurrency operators for petri nets but not for transition systems?

A

!

49
Q

Hw is parallel composition notated?

A

||

50
Q

How is interleaving notated?

A

|||

51
Q

What is the difference between composition, parallel composition, interleaving, complete interleaving, and handshake composition?

A

!

52
Q

How do you interleave two TSes?

A
  • draw the TSes out individually with their states, transitions, and APs
  • find all possible unique pairs of states
  • draw the transitions between the states based upon the changes that cause them in the original TSes
  • eliminate unreachable states
  • eliminate states where only 1 state changes but both would for the same action
  • add APs to each state pair by appending those in states in each individual TS
  • add variable values separately: they don’t interfere; variables stored separately but states combine into pars

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