The DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
Symbolic Model Checking without BDDs
Open accessAbstract
Symbolic Model Checking [3, 14] has proven to be a powerful technique for the verification of reactive systems. BDDs [2] have traditionally been used as a symbolic representation of the system. In this paper we show how boolean decision procedures, like Stalmarck's Method [16] or the Davis & Putnam Procedure [7], can replace BDDs. This new technique avoids the space blow up of BDDs, generates counterexamples much faster, and sometimes speeds up the verification. In addition, it produces counterexamples of minimal length. We introduce a bounded model checking procedure for LTL which reduces model checking to propositional satisfiability. We show that bounded LTL model checking can be done without a tableau construction. We have implemented a model checker BMC, based on bounded model checking, and preliminary results are presented.
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
Graph-Based Algorithms for Boolean Function Manipulation
Bryant (1986) · IEEE Transactions on Computers · doi:10.1109/tc.1986.1676819 · Cited by 8,891
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-citationA Computing Procedure for Quantification Theory
Davis, M., & Putnam, H. (1960) · Journal of the ACM · doi:10.1145/321033.321034 · Cited by 2,647
McMillan, K. L. (1993) · Springer eBooks · doi:10.1007/978-1-4615-3190-6 · Cited by 1,677
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-citationThe 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-citationSymbolic model checking: an approach to the state explosion problem
McMillan, K. L. (1992) · Defense Technical Information Center (DTIC) · Cited by 979
Pushing the envelope: planning, propositional logic, and stochastic search
Kautz, H., & Selman, B. (1996) · Cited by 830
Cited by
Chaff: engineering an efficient SAT solver
Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., & Malik, S. (2001) · Proceedings of the 38th conference on Design automation - DAC '01 · doi:10.1145/378239.379017 · Cited by 2,940
NuSMV 2: An OpenSource Tool for Symbolic Model Checking
Cimatti, A., Clarke, E., Giunchiglia, E., Giunchiglia, F., Pistore, M., Roveri, M., Sebastiani, R., & Tacchella, A. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45657-0_29 · Cited by 1,654
Self-citationHandbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
A Tool for Checking ANSI-C Programs
Clarke, E., Kroening, D., & Lerda, F. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24730-2_15 · Cited by 1,408
Self-citationBiere, A., Cimatti, A., Clarke, E. M., Strichman, O., & Zhu, Y. (2003) · Advances in Computers · doi:10.1016/s0065-2458(03)58003-2 · Cited by 952
Self-citationInterpolation and SAT-Based Model Checking
McMillan, K. L. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45069-6_1 · Cited by 908
Handbook of Knowledge Representation
(2008) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(07)x0300-6 · Cited by 883
Slither: A Static Analysis Framework for Smart Contracts
Feist, J., Grieco, G., & Groce, A. (2019) · 2019 IEEE/ACM 2nd International Workshop on Emerging Trends in Software Engineering for Blockchain (WETSEB) · doi:10.1109/wetseb.2019.00008 · Cited by 872
SAT-Based Model Checking without Unrolling
Bradley, A. R. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-18275-4_7 · Cited by 548
The nuXmv Symbolic Model Checker
Cavada, R., Cimatti, A., Dorigatti, M., Griggio, A., Mariotti, A., Micheli, A., Mover, S., Roveri, M., & Tonetta, S. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-08867-9_22 · Cited by 545
Self-citationTemporal Induction by Incremental SAT Solving
Eén, N., & Sörensson, N. (2003) · Electronic Notes in Theoretical Computer Science · doi:10.1016/s1571-0661(05)82542-3 · Cited by 382
A Survey of Automated Techniques for Formal Software Verification
D'Silva, V., Kroening, D., & Weissenbacher, G. (2008) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2008.923410 · Cited by 378
Debugging the data plane with anteater
Mai, H., Khurshid, A., Agarwal, R., Caesar, M., Godfrey, P. B., & King, S. T. (2011) · Proceedings of the ACM SIGCOMM 2011 conference · doi:10.1145/2018436.2018470 · Cited by 365
Approximate Probabilistic Model Checking
Hérault, T., Lassaigne, R., Magniette, F., & Peyronnet, S. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24622-0_8 · Cited by 295
Behavioral consistency of C and verilog programs using bounded model checking
Clarke, E., Kroening, D., & Yorav, K. (2003) · Proceedings of the 40th annual Design Automation Conference · doi:10.1145/775832.775928 · Cited by 281
Self-citationA survey of recent advances in SAT-based formal verification
Prasad, M. R., Biere, A., & Gupta, A. (2005) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-004-0183-4 · Cited by 279
Self-citationThe Quest for Efficient Boolean Satisfiability Solvers
Zhang, L., & Malik, S. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45657-0_2 · Cited by 279
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
A Promising Path Towards Autoformalization and General Artificial Intelligence
Szegedy, C. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-53518-6_1 · Cited by 29
Computational Complexity of Quadratic Unconstrained Binary Optimization
Yasuoka, H. (2021) · arXiv · doi:10.48550/arxiv.2109.10048
Metadata
- Authors
- Biere, A., Cimatti, A., Clarke, E., & Zhu, Y.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 1999
- Pages
- 193-207
- ISSN
- 0302-9743 (ISSN-L)
- OpenAlex
- W1787074469
- Cited by
- 2,150
- References
- 15
- FWCI
- 41.99
- Type
- conference paper
- Language
- en
- Open access
- green
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.