The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Knowledge compilation and theory approximation
Open accessAbstract
Computational efficiency is a central concern in the design of knowledge representation systems. In order to obtain efficient systems, it has been suggested that one should limit the form of the statements in the knowledge base or use an incomplete inference mechanism. The former approach is often too restrictive for practical applications, whereas the latter leads to uncertainty about exactly what can and cannot be inferred from the knowledge base. We present a third alternative, in which knowledge given in a general representation language is translated (compiled) into a tractable form—allowing for efficient subsequent query answering. We show how propositional logical theories can be compiled into Horn theories that approximate the original information. The approximations bound the original theory from below and above in terms of logical strength. The procedures are extended to other tractable languages (for example, binary clauses) and to the first-order case. Finally, we demonstrate the generality of our approach by compiling concept descriptions in a general frame-based language into a tractable form.
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
(1979) · Cited by 43,841
Lecture Notes in Artificial Intelligence
Brézillon, P., & Bouquet, P. (1999) · Cited by 7,473
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
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
A Computing Procedure for Quantification Theory
Davis, M., & Putnam, H. (1960) · Journal of the ACM · doi:10.1145/321033.321034 · Cited by 2,647
Proceedings of the 16th international joint conference on Artificial Intelligence - IJCAI '99
Colton, S., Bundy, A., & Walsh, T. (1999) · Cited by 2,500
Encyclopedia of Artificial Intelligence
(2009) · IGI Global eBooks · doi:10.4018/978-1-59904-849-9 · Cited by 1,396
On the Complexity of Derivation in Propositional Calculus
Tseitin, G. S. (1983) · Springer eBooks · doi:10.1007/978-3-642-81955-1_28 · Cited by 1,211
A new method for solving hard satisfiability problems
Selman, B., Levesque, H. J., & Mitchell, D. G. M. (1992) · Cited by 1,156
Self-citationPlanning in a hierarchy of abstraction spaces
Sacerdoti, E. D. (1974) · Artificial Intelligence · doi:10.1016/0004-3702(74)90026-5 · Cited by 1,155
Kautz, H., & Selman, B. (1992) · European Conference on Artificial Intelligence · Cited by 1,145
Self-citationReadings in Knowledge Representation
Brachman, R. J., & Levesque, H. J. (1985) · Medical Entomology and Zoology · Cited by 1,041
Linear-time algorithms for testing the satisfiability of propositional horn formulae
Dowling, W. F., & Gallier, J. H. (1984) · The Journal of Logic Programming · doi:10.1016/0743-1066(84)90014-1 · Cited by 1,013
Pengi: an implementation of a theory of activity
Agre, P. E., & Chapman, D. (1987) · National Conference on Artificial Intelligence · Cited by 897
A linear-time algorithm for testing the truth of certain quantified boolean formulas
Aspvall, B., Plass, M. F., & Tarjan, R. E. (1979) · Information Processing Letters · doi:10.1016/0020-0190(79)90002-4 · Cited by 892
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
NP is as easy as detecting unique solutions
Valiant, L. G., & Vazirani, V. V. (1986) · Theoretical Computer Science · doi:10.1016/0304-3975(86)90135-0 · Cited by 635
Critical Behavior in the Satisfiability of Random Boolean Expressions
Kirkpatrick, S., & Selman, B. (1994) · Science · doi:10.1126/science.264.5163.1297 · Cited by 589
Self-citationA logic of implicit and explicit belief
Levesque, H. J. (1984) · Cited by 560
A Catalog of Complexity Classes
JOHNSON, D. S. (1990) · Algorithms and Complexity · doi:10.1016/b978-0-444-88071-0.50007-2 · Cited by 556
Universal plans for reactive robots in unpredictable environments
Schoppers, M. (1987) · Cited by 476
Machine Invention of First-order Predicates by Inverting Resolution
MUGGLETON, S., & BUNTINE, W. (1988) · Machine Learning Proceedings 1988 · doi:10.1016/b978-0-934613-64-4.50040-2 · Cited by 436
Handbook of theoretical computer science
Czerbo, D. B. (1992) · Artificial Intelligence in Medicine · doi:10.1016/0933-3657(92)90044-p · Cited by 338
Found ations of assumption-based truth maintenance systems: preliminary report
Reiter, R., & de Kleer, J. (1987) · National Conference on Artificial Intelligence · Cited by 300
Generating hard satisfiability problems
Selman, B., Mitchell, D. G., & Levesque, H. J. (1996) · Artificial Intelligence · doi:10.1016/0004-3702(95)00045-3 · Cited by 296
Self-citationSolving time-dependent planning problems
Boddy, M., & Dean, T. (1989) · International Joint Conference on Artificial Intelligence · Cited by 292
Domain-independent extensions to GSAT: solving large structured satisfiability problems
Selman, B., & Kautz, H. (1993) · Cited by 291
Self-citationOn Representations of Problems of Reasoning about Actions
Amarel, S. (1981) · Elsevier eBooks · doi:10.1016/b978-0-934613-03-3.50006-4 · Cited by 264
The Complexity of Finite Functions
BOPPANA, R. B., & SIPSER, M. (1990) · Algorithms and Complexity · doi:10.1016/b978-0-444-88071-0.50019-9 · Cited by 251
Making believers out of computers
Levesque, H. J. (1986) · Artificial Intelligence · doi:10.1016/0004-3702(86)90068-8 · Cited by 228
Experimental results on the crossover point in satisfiability problems
Crawford, J. M., & Auton, L. D. (1993) · Cited by 209
Doyle, J., & Patil, R. S. (1991) · Artificial Intelligence · doi:10.1016/0004-3702(91)90029-j · Cited by 168
Complexity results for planning
Bylander, T. (1991) · International Joint Conference on Artificial Intelligence · Cited by 167
A logical framework for depiction and image interpretation
Reiter, R., & Mackworth, A. K. (1989) · Artificial Intelligence · doi:10.1016/0004-3702(89)90008-8 · Cited by 149
Knowledge compilation using horn approximations
Selman, B., & Kautz, H. (1991) · Cited by 140
Self-citationStructure identification in relational data
Dechter, R., & Pearl, J. (1992) · Artificial Intelligence · doi:10.1016/0004-3702(92)90009-m · Cited by 130
Renaming a Set of Clauses as a Horn Set
Lewis, H. R. (1978) · Journal of the ACM · doi:10.1145/322047.322059 · Cited by 129
Critical behavior in the computational cost of satisfiability testing
Selman, B., & Kirkpatrick, S. (1996) · Artificial Intelligence · doi:10.1016/0004-3702(95)00056-9 · Cited by 129
Self-citationReflection and Action Under Scarce Resources: Theoretical Principles and Empirical Study
Horvitz, E., Cooper, G. F., & Heckerman, D. E. (1989) · Cited by 126
A completeness theorem and a computer program for finding theorems derivable from given axioms
Lee, C.-T. (1967) · University of California, Berkeley eBooks · Cited by 98
Khardon, R., & Roth, D. (1997) · Journal of the ACM · doi:10.1145/265910.265918 · Cited by 82
Complexity results for blocks-world planning
Gupta, N. C., & Nau, D. S. (1991) · National Conference on Artificial Intelligence · Cited by 63
Semantical and computational aspects of Horn approximations
Cadoli, M., & Scarcello, F. (2000) · Artificial Intelligence · doi:10.1016/s0004-3702(00)00010-2 · Cited by 52
On the complexity of domain-independent planning
Erol, K., Nau, D. S., & Subrahmanian, V. S. (1992) · Cited by 45
Near-Optimal Plans, Tractability, and Reactivity
Selman, B. (1994) · Principles of Knowledge Representation and Reasoning · doi:10.1016/b978-1-4832-1452-8.50143-3 · Cited by 32
Self-citationValiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Cited by
Working Models for Uncertain Data
Sarma, A. D., Benjelloun, O., Halevy, A., & Widom, J. (2006) · 22nd International Conference on Data Engineering (ICDE'06) · doi:10.1109/icde.2006.174 · Cited by 344
Metadata
- Authors
- Selman, B., & Kautz, H.
- Venue
- Journal of the ACM
- Published
- 1996-03
- Volume
- 43
- Issue
- 2
- Pages
- 193-224
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2038897673
- Cited by
- 295
- References
- 46
- FWCI
- 14.90
- 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.