The patterns provided in this system cover a broad range of requirements for real systems. Your requirement, however, may require you to adapt existing patterns slightly to better express your intended property. There are a number of ways in which this variation can take place, e.g., parameterization of patterns, combination of patterns, and variation in pattern scopes.
[]!init
responds to init
globally would beshutdown
state we would like it to
be the case that request
s are respond
ed to.
We know that a succesful response has the form:<>
operator when embedded in the scope
does not take into account the fact that the search for respond
should
terminate upon encountering shutdown
. One can modify this by
expanding the <>
to its until form, e.g., true U respond
,
then requiring that throughout the search the shutdown
is
absent (this is similar to the constrained response discussed below).
The resulting formula is:The first of these alternatives corresponds to the checking of individual property specifications independently and disjoining the results. This is true for all specification formalisms. The latter situation can be achieved in formalisms that allow specifications to be disjoined under the same universal path quantifier.
For LTL and QREs there is an implicit outer universal path quantifier, thus checking of a top-level disjunction of specifications will achieve these semantics. To achieve the first alternative (above) one must check LTL and QRE specifications separately.
This is not the case for CTL, where two specifications cannot be disjoined directly under the same path quantifier. A top-level disjunction CTL achieves the first alternative and the second cannot be achieved directly (although one might be able to rewrite a combined version of the two specifications).
We have chosen to define scopes for state-based formalisms that
include the state marking the beginning of the scope but do not
include the state marking the end of the scope. Thus, for example,
the LTL version of this specification would be
[]((Q & o<>R) -> (!P & o((!P) U (R | [](!P)))))
which requires that
P be false in the state where Q holds
but does not require P to be false when
R becomes true. We chose these closed-left/open-right
scopes because they are relatively easy to encode in specifications
and beacuse they work for the real property specifications we
studied.
It isn't very hard, however, to modify the mappings to open the scope
on the left or close it on the right. An LTL specification of the
"P is absent between Q and
R" property with a scope that is open on the left
would simply remove the first !P:
[]((Q & o<>R) -> (o((!P) U (R | [](!P)))))
allowing P to
hold at the state marking the beginning of the scope. Similarly, to
close the scope on the right, we have to require !P to
hold until a state in which both R and
!P are true:
[]((Q & o<>R) -> (!P & o((!P) U ((R & (!P))| [](!P)))))
Similar modifications can be made to adjust all the mappings for the various versions of the scopes.
The plain response pattern
also has a constrained variation. For example, one
can restrict Z
from the region between P and the S that responds
to it in LTL, but converting the <>
to its U
equivalent then embedding !Z in its left operand. The global
response mapping:
[](P -> <>S)becomes:
[](P -> (true U S))and finally:
[](P -> (!Z U S))A similar transformation to the
<>
in the after scope
can be applied. The before, between and after-until scope versions
of the LTL response mappings already unfold the <>
to
its U
form. In these cases, one need only embed the !Z
in the proper place (which is identified by looking for the S
appearing as the right operand of the U
). For example, the
between response mapping :[]((Q & <>R) -> (P -> (!R U S)) U R)becomes:
[]((Q & <>R) -> (P -> ((!R & !Z) U S)) U R)
Modifications for mappings in other formalisms can be applied as well. Global and between scope versions of constrained response in CTL are:
AG(P -> A[!Z U S]) AG(Q -> !E[!R U (P & !R & (E[!S U R] | E[Z U S]))])The global version mirrors the LTL modifications. The between scope version is different because the CTL spec is expressed in terms of the lack of a violating sequence. In this case, we must enumerate the possible violating sequences, i.e., a missing response
E[!S U R]
or the occurrence of a constrained
state before the response E[Z U S]
.
Global and between scope versions of constrained response as QREs are:
[-P]*; (P; [-S,Z]*; S; [-P]*)* [-Q]*; (Q; [-P,R]*; (P; [-S,R,Z]*; S; [-P,R]*)*; R; [-Q]*)*; (Q; [-R]*)?
Multiple propositions can embedded in the constraint by using conjunction in the logics and by listing multiple events in QREs.
It is important to note that constrained response is different from absence with a between scope. The latter, which in LTL is:
[]((Q & <>R) -> !P U R)does not require the closing of the scope (which corresponds to the responding state).