Specification of communicating processes: temporal logic versus refusals-based refinement

Journal article

In this paper we consider the relationship between refinement-oriented specification and specifications using a temporal logic. We investigate the extent to which one can check whether a program in a process algebra, such as Communicating Sequential Processes (CSP), satisfies a temporal logic specification using a refinement-based model checker, such as FDR. We consider what atomic formulae are appropriate in a temporal logic for specifying communicating processes, in particular where one wants to talk about the availability of events. We then show that, perhaps surprisingly, the standard stable failures model is not adequate for capturing specifications in such a logic: instead the refusal traces model must be used. We formalise the logic by giving it a semantics in this model. We show that the temporal operators eventually and until, and negation, cannot, in general, be tested for via simple refinement checks. For the remaining fragment of the logic, we present a translation into simple refinement checks. Finally, we show that refusal traces equivalence is characterised by a slightly augmented version of that fragment. © 2007 British Computer Society.

Authors: Lowe, G

• Publication status: Published
• Journal: FORMAL ASPECTS OF COMPUTING
• Volume: 20
• Issue: 3
• Pages: 277-294
• Publication date: 2008-05-01
• DOI: 10.1007/s00165-007-0065-0
• EISSN: 1433-299X
• ISSN: 0934-5043
• Language: English
• Keywords: CSP; refusals; specification; temporal logic; refinement testing