The DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
Combinational test generation using satisfiability
Abstract
We present a robust, efficient algorithm for combinational test generation using a reduction to satisfiability (SAT). The algorithm, Test Generation Using Satisfiability (TEGUS), solves a simplified test set characteristic equation using straightforward but powerful greedy heuristics, ordering the variables using depth-first search and selecting a variable from the next unsatisfied clause at each branching point. For difficult faults, the computation of global implications is iterated, which finds more implications than previous approaches and subsumes structural heuristics such as unique sensitization. Without random tests or fault simulation, TEGUS completes on every fault in the ISCAS networks, demonstrating its robustness, and is ten times faster for those networks which have been completed by previous algorithms. Our implementation of TEGUS can be used as a base line for comparing test generation algorithms; we present comparisons with 45 recently published algorithms. TEGUS combines the advantages of the elegant organization of SAT-based algorithms with the efficiency of structural algorithms.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
(1979) · Cited by 43,841
Computer Architecture: A Quantitative Approach
Hennessy, J. L., & Patterson, D. A. (1989) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 9,370
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
Combinational profiles of sequential benchmark circuits
Brglez, F., Bryan, D., & Kozminski, K. (2003) · IEEE International Symposium on Circuits and Systems · doi:10.1109/iscas.1989.100747 · Cited by 2,095
A neutral netlist of 10 combinational benchmark circuits and a target translator in FORTRAN
Brglez, F. (1985) · Cited by 1,273
Random number generators: good ones are hard to find
Park, S. K., & Miller, K. W. (1988) · Communications of the ACM · doi:10.1145/63039.63042 · Cited by 1,262
An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits
Goel (1981) · IEEE Transactions on Computers · doi:10.1109/tc.1981.1675757 · Cited by 1,122
Test pattern generation using Boolean satisfiability
Larrabee, T. (1992) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.108614 · Cited by 703
Polynomially Complete Fault Detection Problems
Ibarra, Ó. H., & Sahni, S. K. (1975) · IEEE Transactions on Computers · doi:10.1109/t-c.1975.224205 · Cited by 264
Kunz, W., & Pradhan, D. K. (1994) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.310903 · Cited by 214
Cited by
GRASP: a search algorithm for propositional satisfiability
Marques-Silva, J. P., & Sakallah, K. A. (1999) · IEEE Transactions on Computers · doi:10.1109/12.769433 · Cited by 1,374
Symbolic Model Checking without BDDs
Biere, A., Cimatti, A., Clark, E., & Zhu, Y. (1999) · doi:10.21236/ada360973 · Cited by 537
Three Scheduling Algorithms Applied to the Earth Observing Systems Domain
Wolfe, W. J., & Sorensen, S. E. (2000) · Management Science · doi:10.1287/mnsc.46.1.148.15134 · Cited by 313
The 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
(2005) · Cited by 38
Metadata
- Authors
- Stephan, P., Brayton, R. K., & Sangiovanni-Vincentelli, A. L.
- Venue
- IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Published
- 1996
- Volume
- 15
- Issue
- 9
- Pages
- 1167-1176
- ISSN
- 0278-0070 (ISSN-L)
- OpenAlex
- W2135613306
- Cited by
- 326
- References
- 21
- FWCI
- 17.10
- Type
- journal article
- Language
- en
- Open access
- closed
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Combinational test generation using satisfiability. https://app.cochat.ai/papers/10.1109/43.536723
- The paper
- Stephan, P., Brayton, R. K., & Sangiovanni-Vincentelli, A. L. (1996). Combinational test generation using satisfiability. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. https://doi.org/10.1109/43.536723
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.
