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
COMPACTEST: a method to generate compact test sets for combinational circuits
Pomeranz, I., Reddy, L. N., & Reddy, S. M. (1993) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.238040 · Cited by 213
A transitive closure algorithm for test generation
Chakradhar, S. T., Agrawal, V. D., & Rothweiler, S. G. (1993) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.238038 · Cited by 172
Efficient generation of test patterns using Boolean difference
Larrabee, T. (2003) · IEEE International Test Conference (ITC) · doi:10.1109/test.1989.82368 · Cited by 85
ATPG for ultra-large structured designs
Waicukauski, J. A., Shupe, P. A., Giramma, D., & Matin, A. (2002) · IEEE International Test Conference (ITC) · doi:10.1109/test.1990.113999 · Cited by 68
A small test generator for large designs
Kundu, S. K., Huisman, L. M., Nair, I., Ivenaar, V., & Reddy, L. (1992) · IEEE International Test Conference (ITC) · doi:10.1109/test.1992.527801 · Cited by 54
One-pass redundancy identification and removal
Abramovici, M., & Iyer, M. A. (1992) · IEEE International Test Conference (ITC) · doi:10.1109/test.1992.527904 · Cited by 35
Dynamic redundancy identification in automatic test generation
Abramovici, M., Miller, D. T., & Roy, R. (1992) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.124427 · Cited by 26
TSUNAMI: a path oriented scheme for algebraic test generation
Stanion, T., & Bhattacharya, D. (2002) · IEEE International Symposium on Fault-Tolerant Computing · doi:10.1109/ftcs.1991.146630 · Cited by 26
Contest: a fast ATPG tool for very large combinational circuits
Mahlstedt, U., Grüning, T., Ozcan, C., & Daehn, W. (2002) · International Conference on Computer Aided Design · doi:10.1109/iccad.1990.129886 · Cited by 24
Test pattern generation with restrictors
Konijnenburg, M., van der Linden, J. T., & van de Goor, A. J. (2002) · IEEE International Test Conference (ITC) · doi:10.1109/test.1993.470644 · Cited by 18
A method for reducing the search space in test pattern generation
Teramoto, M. (2002) · IEEE International Test Conference (ITC) · doi:10.1109/test.1993.470669 · Cited by 12
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
Symbolic Model Checking without BDDs
Biere, A., Cimatti, A., Clarke, E., & Zhu, Y. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49059-0_14 · Cited by 2,150
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
SATzilla: Portfolio-based Algorithm Selection for SAT
Xu, L., Hutter, F., Hoos, H. H., & Leyton-Brown, K. (2008) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2490 · Cited by 857
Symbolic Model Checking without BDDs
Biere, A., Cimatti, A., Clark, E., & Zhu, Y. (1999) · doi:10.21236/ada360973 · Cited by 537
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
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.