1. Home
  2. Model checking concurrent
  3. Model checking concurrent
  4. Using temporal logic to specify

0.5 Using temporal logic to specify properties  (Page 6/11)

<< Chapter < Page
  Model checking concurrent     Page 6 / 11
Chapter >> Page >

As a more complicated variation, we generally want to match requests and their servicing. For example, what if there are tworequests, r 1 and r 2 , arriving in that order?In a particular context, do we expect that there are also exactly two servicings, s 1 and s 2 ? If so, do we also expect them in that order?

As a partial solution, how can we express ``whenever r 1 , s 1 will happen before s 2 ''?

If we are also requiring that s 2 indeed actually happen, then we can use the following: □ ( ( r 1 ◇ s 2 ) ( s 2 U s 1 ) ) .

Note that since LTL does not have quantifiers (like and) we cannot use variable indexing in our formulas.In other words, we can't talk about r i and s j , but instead, must always refer to specific variables like r 1 and s 2 .

From these examples and the ones following, we can see that English is typically too ambiguous. To get the appropriatelogic formula, we need to go back to the original problem and determine what was truly meant.Formalizing your specifications into temporal logic gives you the opportunity to closely examine what those specificationsreally should be.

Given a formula, try to understand it by translating it into English. Providing sample timelines that satisfy the formulais also quite helpful.

Describe the meaning of □ ◇ p in words and a timeline.

Literally, we can simply say ``always, eventually p ''. While that phrase is fairly common among logicians, it's not very natural ormeaningful to most people. A clearer, but more long-winded, equivalent is``at any point in time, p will happen in the future''.

More concise, though, is `` p happens infinitely often''. To understand that, consider a timeline. In words, at any time t 0 , p will happen sometime in the future; call that time t 1 . And at moment t 1 +1, p will happen sometime in the future; call that t 2 . Repeat forever.

The beginning of a trace where p happens infinitely often.

Describe the meaning of □ ( q □ p ) in words and a timeline.

Again, a literal translation is ``always, if q then always not p''.Correct, but a bit more idiomatic-English would be ``whenever q, then forever not p'' or``Once q, p is forever false''.

The beginning of a trace satisfying the property.

A railroad wants to make a new controller for single-track railroad crossings.Naturally, they don't want any accidents with cars at the crossing, so they want to verify their controller.Their propositions Prop include train_is_approaching , train_is_crossing , light_is_flashing , and gate_is_down .

Brainstorming: Using natural English, what are some propertieswe'd like to have true? Feel free to use words like ``always'', ``eventually'',``while'', and ``until''. You may add new propositions to Prop , if you think it's appropriate.

For each, feel free to demonstrate that the one property is not sufficient:give a trace which satisfies the property but is either unacceptable or unrealistic.(For instance, ``the gate is always down'' is safe but unacceptable;``a train is always crossing'' is unrealistic since there aren't infinite trains.)

We can think of lots of examples, such as these.

  • Whenever a train passing, the gate is down.
  • If a train is approaching or passing, then the light is flashing.
  • If the gate is up and the light is not flashing, then no train is passing or approaching.
  • If a train is approaching, the gate will be down before the train passes.
  • If a train has finished passing, then later the gate will be up.
  • The gate will be up infinitely many times.
  • If a train is approaching, then it will be passing, and later itwill be done passing with no train approaching. (Thus, trains aren't infinitely long, and thereare gaps between the trains.)
<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Model checking concurrent programs. OpenStax CNX. Oct 27, 2005 Download for free at http://cnx.org/content/col10294/1.3
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Model checking concurrent programs' conversation and receive update notifications?

Ask