ACTLW - an action-based computation tree logic with unless operator

Robert Meolic (Author), Tatjana Kapus (Author), Zmago Brezočnik (Author)

Abstract

Model checkers for systems represented by labelled transition systems are not as extensively used as those for systems represented by Kripke structures. This is partially due to the lack of an elegant formal language for property specification which would not be as raw as, for example, HML yet also not as complex as, for example, -calculus. This paper proposes a new action-based propositional branching-time temporal logic ACTLW, which enhances popular computation tree logic (CTL) with the notion of actions in a similar but more comprehensive way than action-based CTL introduced by De Nicola and Vaandrager [R. De Nicola, F.W. Vaandrager, Action versus logics for transition systems, in: Semantics of Systems of Concurrent Processes, Proceedings LITP Spring School on Theoretical Computer Science, LNCS 469, 1990, pp. 407-419]. ACTLW is defined by using temporal operators until and unless only, whereas all other temporal operators are derived from them. Fixed-point characterisation of the operators together with symbolic algorithms for globalmodel checking are shown. Usage of this new logic is illustrated by an example of verification of mutual-exclusion algorithms.

Keywords

formalna verifikacija;model za preverjanje;algoritmi;formal verification;model checking;action-based temporal logic;fixed point;mutual-exclusion algorithm;

Data

Language:	English
Year of publishing:	2008
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
UDC:	004.92
COBISS:	12047638
ISSN:	0020-0255
Views:	1766
Downloads:	91
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary keywords:	formalna verifikacija;model za preverjanje;algoritmi;
URN:	URN:SI:UM:
Pages:	str. 1542-1557
Volume:	ǂVol. ǂ178
Issue:	ǂiss. ǂ6
Chronology:	2008
ID:	8718602