The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
Automatic verification of finite-state concurrent systems using temporal logic specifications
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Communicating Sequential Processes
Hoare, T. (1985) · Cited by 9,016
On observing nondeterminism and concurrency
Hennessy, M., & Milner, R. (1980) · Lecture Notes in Computer Science · doi:10.1007/3-540-10003-2_79 · Cited by 4,492
Specification and verification of concurrent systems in CESAR
Queille, J. P., & Sifakis, J. (1982) · Lecture Notes in Computer Science · doi:10.1007/3-540-11494-7_22 · Cited by 1,321
The complexity of propositional linear temporal logics
Sistla, A. P., & Clarke, E. M. (1985) · Journal of the ACM · doi:10.1145/3828.3837 · Cited by 1,095
Self-citationDESIGN AND SYNTHESIS OF SYNCHRONIZATION SKELETONS USING BRANCHING TIME TEMPORAL LOGIC
Clarke, E. M., & Emerson, E. A. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-69850-0_12 · Cited by 1,070
Self-citation“Sometimes” and “not never” revisited: on branching versus linear time temporal logic
Emerson, E. A., & Halpern, J. Y. (1986) · Journal of the ACM · doi:10.1145/4904.4999 · Cited by 1,009
Self-citationOn the temporal analysis of fairness
Gabbay, D. M., Pnueli, A., Shelah, S., & Stavi, J. (1980) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/567446.567462 · Cited by 732
Using branching time temporal logic to synthesize synchronization skeletons
Emerson, E. A., & Clarke, E. M. (1982) · Science of Computer Programming · doi:10.1016/0167-6423(83)90017-5 · Cited by 660
Self-citationProving Liveness Properties of Concurrent Programs
Owicki, S., & Lamport, L. (1982) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357172.357178 · Cited by 576
Cited by
Statecharts: a visual formalism for complex systems
Harel, D. (1987) · Science of Computer Programming · doi:10.1016/0167-6423(87)90035-9 · Cited by 6,751
Clarke, E., McMillan, K., Campos, S., & Hartonas-Garmhausen, V. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-61474-5_93 · Cited by 2,839
Self-citationSymbolic model checking: 1020 States and beyond
Burch, J. R., Clarke, E. M., McMillan, K. L., Dill, D. L., & Hwang, L. J. (1992) · Information and Computation · doi:10.1016/0890-5401(92)90017-a · Cited by 2,703
Self-citationEMERSON, E. A. (1990) · Formal Models and Semantics · doi:10.1016/b978-0-444-88074-1.50021-4 · Cited by 2,585
Self-citationSymbolic Boolean manipulation with ordered binary-decision diagrams
Bryant, R. E. (1992) · ACM Computing Surveys · doi:10.1145/136035.136043 · Cited by 2,015
The synchronous data flow programming language LUSTRE
Halbwachs, N., Caspi, P., Raymond, P., & Pilaud, D. (1991) · Proceedings of the IEEE · doi:10.1109/5.97300 · Cited by 1,590
On the synthesis of a reactive module
Pnueli, A., & Rosner, R. (1989) · Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '89 · doi:10.1145/75277.75293 · Cited by 1,432
Alternating-time temporal logic
Alur, R., Henzinger, T. A., & Kupferman, O. (2002) · Journal of the ACM · doi:10.1145/585265.585270 · Cited by 1,394
Smart cars on smart roads: problems of control
Varaiya, P. (1993) · IEEE Transactions on Automatic Control · doi:10.1109/9.250509 · Cited by 1,383
A logic for reasoning about time and reliability
Hansson, H., & Jonsson, B. (1994) · Formal Aspects of Computing · doi:10.1007/bf01211866 · Cited by 1,372
A formal basis for architectural connection
Allen, R., & Garlan, D. (1997) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/258077.258078 · Cited by 1,253
Model checking and abstraction
Clarke, E. M., Grumberg, O., & Long, D. E. (1994) · ACM Transactions on Programming Languages and Systems · doi:10.1145/186025.186051 · Cited by 1,211
Self-citationFormal Methods: State of the Art and Future Directions
Clarke, E., Wing, J. M., & Jones, C. B. (1996) · doi:10.25405/ncl.34123050 · Cited by 1,122
Self-citationCounterexample-guided abstraction refinement for symbolic model checking
Clarke, E., Grumberg, O., Jha, S., Lu, Y., & Veith, H. (2003) · Journal of the ACM · doi:10.1145/876638.876643 · Cited by 994
Self-citationAutomata for modeling real-time systems
Alur, R., & Dill, D. (2005) · Lecture Notes in Computer Science · doi:10.1007/bfb0032042 · Cited by 904
Model-checking for real-time systems
Alur, R., Courcoubetis, C., & Dill, D. (2002) · [1990] Proceedings. Fifth Annual IEEE Symposium on Logic in Computer Science · doi:10.1109/lics.1990.113766 · Cited by 897
Model checking for programming languages using VeriSoft
Godefroid, P. (1997) · Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '97 · doi:10.1145/263699.263717 · Cited by 825
Model-checking algorithms for continuous-time markov chains
Baier, C., Haverkort, B., Hermanns, H., & Katoen, J.-P. (2003) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2003.1205180 · Cited by 767
Formal methods: state of the art and future directions
Clarke, E. M., & Wing, J. M. (1996) · ACM Computing Surveys · doi:10.1145/242223.242257 · Cited by 763
Self-citationA specifier's introduction to formal methods
Wing, J. M. (1990) · Computer · doi:10.1109/2.58215 · Cited by 736
The benefits of relaxing punctuality
Alur, R., Feder, T., & Henzinger, T. A. (1991) · Proceedings of the tenth annual ACM symposium on Principles of distributed computing - PODC '91 · doi:10.1145/112600.112613 · Cited by 679
Automated consistency checking of requirements specifications
Heitmeyer, C. L., Jeffords, R. D., & Labaw, B. G. (1996) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/234426.234431 · Cited by 605
Managing conflicts in goal-driven requirements engineering
van Lamsweerde, A., Darimont, R., & Letier, E. (1998) · IEEE Transactions on Software Engineering · doi:10.1109/32.730542 · Cited by 595
Kwiatkowska, M., Norman, G., & Parker, D. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-72522-0_6 · Cited by 590
Abstractions for network update
Reitblatt, M., Foster, N., Rexford, J., Schlesinger, C., & Walker, D. (2012) · Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/2342356.2342427 · Cited by 584
Model Checking of Safety Properties
Kupferman, O., & Vardi, M. Y. (2001) · Formal Methods in System Design · doi:10.1023/a:1011254632723 · Cited by 566
Recognizing safety and liveness
Alpern, B., & Schneider, F. B. (1987) · Distributed Computing · doi:10.1007/bf01782772 · Cited by 557
Requirements specification for process-control systems
Leveson, N. G., Heimdahl, M. P. E., Hildreth, H., & Reese, J. D. (1994) · IEEE Transactions on Software Engineering · doi:10.1109/32.317428 · Cited by 556
Logics and models of real time: A survey
Alur, R., & Henzinger, T. A. (1992) · Lecture Notes in Computer Science · doi:10.1007/bfb0031988 · Cited by 548
Memory-efficient algorithms for the verification of temporal properties
Courcoubetis, C., Vardi, M., Wolper, P., & Yannakakis, M. (1992) · Formal Methods in System Design · doi:10.1007/bf00121128 · Cited by 501
Property specification patterns for finite-state verification
Dwyer, M. B., Avrunin, G. S., & Corbett, J. C. (1998) · Proceedings of the second workshop on Formal methods in software practice - FMSP '98 · doi:10.1145/298595.298598 · Cited by 459
Characterizing finite Kripke structures in propositional temporal logic
Browne, M. C., Clarke, E. M., & Grümberg, O. (1988) · Theoretical Computer Science · doi:10.1016/0304-3975(88)90098-9 · Cited by 419
Self-citationProbabilistic Verification of Discrete Event Systems Using Acceptance Sampling
Younes, H. L. S., & Simmons, R. G. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45657-0_17 · Cited by 373
Formalizing architectural connection
Allen, R. J., & Garlan, D. (1994) · KiltHub Repository · doi:10.5555/257734.257745 · Cited by 364
Using formal specifications to support testing
Hierons, R. M., Bogdanov, K., Bowen, J. P., Cleaveland, R., Derrick, J., Dick, J., Gheorghe, M., Harman, M., Kapoor, K., Krause, P., et al. (2009) · ACM Computing Surveys · doi:10.1145/1459352.1459354 · Cited by 356
Structured control for autonomous robots
Simmons, R. G. (1994) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.285583 · Cited by 344
On the Decision Problem for Two-Variable First-Order Logic
Grädel, E., Kolaitis, P. G., & Vardi, M. Y. (1997) · Bulletin of Symbolic Logic · doi:10.2307/421196 · Cited by 321
A task description language for robot control
Simmons, R., & Apfelbaum, D. (2002) · Proceedings. 1998 IEEE/RSJ International Conference on Intelligent Robots and Systems. Innovations in Theory, Practice and Applications (Cat. No.98CH36190) · doi:10.1109/iros.1998.724883 · Cited by 318
Real-time specification patterns
Konrad, S., & Cheng, B. H. C. (2005) · Proceedings. 27th International Conference on Software Engineering, 2005. ICSE 2005. · doi:10.1109/icse.2005.1553580 · Cited by 307
Gerevini, A. E., Haslum, P., Long, D., Saetti, A., & Dimopoulos, Y. (2009) · Artificial Intelligence · doi:10.1016/j.artint.2008.10.012 · Cited by 295
Model Checking TLA+ Specifications
Yu, Y., Manolios, P., & Lamport, L. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48153-2_6 · Cited by 286
A Survey of Statistical Model Checking
Agha, G., & Palmskog, K. (2018) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/3158668 · Cited by 285
Formal verification in hardware design: a survey
Kern, C., & Greenstreet, M. R. (1999) · ACM Transactions on Design Automation of Electronic Systems · doi:10.1145/307988.307989 · Cited by 284
A general approach to network configuration verification
Beckett, R., Gupta, A., Mahajan, R., & Walker, D. (2017) · Proceedings of the Conference of the ACM Special Interest Group on Data Communication · doi:10.1145/3098822.3098834 · Cited by 262
Formal Methods for Autonomous Systems
Wongpiromsarn, T., Ghasemi, M., Cubuktepe, M., Bakirtzis, G., Carr, S., Karabag, M. O., Neary, C., Gohari, P., & Topcu, U. (2023) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000029 · Cited by 17
Failures and fixes: a study of software system incident response
Sillito, J., & Kutomi, E. (2020) · 2020 IEEE International Conference on Software Maintenance and Evolution (ICSME) · doi:10.1109/icsme46990.2020.00027 · Cited by 14
Metadata
- Authors
- Clarke, E. M., Emerson, E. A., & Sistla, A. P.
- Venue
- ACM Transactions on Programming Languages and Systems
- Published
- 1986-04
- Volume
- 8
- Issue
- 2
- Pages
- 244-263
- ISSN
- 0164-0925 (ISSN-L)
- 1558-4593
- OpenAlex
- W2117189826
- Cited by
- 3,605
- References
- 14
- FWCI
- 24.81
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.