Abstract
We give an efficient procedure for verifying that a finite-state concurrent system meets a specification expressed in a (propositional, branching-time) temporal logic. Our algorithm has complexity linear in both the size of the specification and the size of the global state graph for the concurrent system. We also show how this approach can be adapted to handle fairness. We argue that our technique can provide a practical alternative to manual proof construction or use of a mechanical theorem prover for verifying many finite-state concurrent systems. Experimental results show that state machines with several hundred states can be checked in a matter of seconds.
Keywords
Computer scienceFinite-state machineLinear temporal logicTemporal logicAutomated theorem provingModel checkingState (computer science)Programming languageTheoretical computer scienceGraphBranching (polymer chemistry)Computation tree logicAlgorithm
Affiliated Institutions
Related Publications
A really temporal logic
A real-time temporal logic for the specification of reactive systems is introduced. The novel feature of the logic, TPTL, is the adoption of temporal operators as quantifiers ov...
Explicit clock temporal logic
The authors present a single exponent decision procedure for the validity of XCTL formulas, and a double exponent decision procedure for the validity of XCTL formulas over finit...
Model-checking for real-time systems
This research extends CTL model-checking to the analysis of real-time systems, whose correctness depends on the magnitudes of the timing delays. For specifications, the syntax o...
The temporal logic of programs
A unified approach to program verification is suggested, which applies to both sequential and parallel programs. The main proof method suggested is that of temporal reasoning in...
Specification and Verification of Communication Protocols in AFFIRM Using State Transition Models
It is becoming increasingly important that communication protocols be formally specified and verified. This paper describes a particular approach–the state transition model–usin...
Publication Info
- Year
- 1986
- Type
- article
- Volume
- 8
- Issue
- 2
- Pages
- 244-263
- Citations
- 3529
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
3529
OpenAlex
Cite This
E. M. Clarke,
E. Allen Emerson,
A. Prasad Sistla
(1986).
Automatic verification of finite-state concurrent systems using temporal logic specifications.
ACM Transactions on Programming Languages and Systems
, 8
(2)
, 244-263.
https://doi.org/10.1145/5397.5399
Identifiers
- DOI
- 10.1145/5397.5399