Knowledge compilation and theory approximation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Knowledge compilation and theory approximation

Full text

Pdf (2.36 MB)

Source

Journal of the ACM (JACM) archive
Volume 43 , Issue 2 (March 1996) table of contents

Pages: 193 - 224

Year of Publication: 1996

ISSN:0004-5411

Authors

Bart Selman	AT&T Bell Labs., Murray Hill, NJ
Henry Kautz	AT&T Bell Labs., Murray Hill, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 61, Citation Count: 61

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/226643.226644 What is a DOI?

ABSTRACT

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	AGRE, P.E., AND CHAPMAN, D. 1987. Pengi: An implementation of a theory of activity. In Proceedings of the 6th National Conference on Artificial Intelligence (Al11-87) (Seattle, Wash.). Morgan-Kaufmann, San Mateo, Calif., pp. 268-272.
	2	AMAREL, S. 1968. On representations of problems of reasoning about actions. In Machine Intelligence, vol. 3, D. Michie, ed. Edinburgh University Press, Edinburgh, Scotland, pp. 131-171.
	3	ASPVALL, B., PLASS, M. F., AND T^RJAN, R.E. 1979. A linear-time algorithm for testing the truth of certain quantified Boolean formulae. Inf. Proc. Left. 8, 121-127.
	4	Ravi B. Boppana , Michael Sipser, The complexity of finite functions, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	5	Alex Borgida , David W. Etherington, Hierarchical knowledge bases and efficient disjunctive reasoning, Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.33-43, December 1989
	6	BuRo, M., AND BONING, H.K. 1992. Report on a SAT competition. Technical Memorandum 110. Mathematik/Informatik Univ. Paderborn, Paderborn, Germany.
	7	BVt. ANr~ER, T. 1991. Complexity results for planning. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI-91) (Sidney, Australia). Morgan-Kaufmann, San Mateo, Calif., pp. 274-279.
	8	CADOLI, M. 1993. Semantical and computational aspects of horn approximations. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI-93) (Chambery, France). Morgan-Kaufmann, San Mateo, Calif., pp. 39-44.
	9	CADOLE, M., AND SC~AERr, M 1992. Approximation in concept description languages. In Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR-92) (Cambridge, Mass.). Morgan-Kaufmann, San Marco, Calif., pp. 330-341.
	10	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	11	CRAWFORD, J., AND AUTON, L. 1993. Experimental results on the crossover point in satisfiability problems. In Proceedings of the llth National Conference of Artificial Intelligence (,4111-93) (Washington, D.C.). MIT Press, Cambridge, Mass., pp. 21-27.
	12	DALAL, M., AND ETHERINGTON, D.W. 1992. Tractable approximate deduction using limited vocabularies. In Proceedings of the 9th Canadian Conference on Artificial Intelligence (,41 '92) (Vancouver, B.C., Canada). Morgan-Kaufmann, Sun Mateo, Calif., pp. 206-212.
	13	Martin Davis , Hilary Putnam, A Computing Procedure for Quantification Theory, Journal of the ACM (JACM), v.7 n.3, p.201-215, July 1960 [doi>10.1145/321033.321034]
	14	DE KLEEg, J. 1990. Exploiting locality in the TMS. In Proceedings of the 8th National Conference on Artificial Intelligence (AAAI-91) (Boston, Mass.). MIT Press, Cambridge, Mass., pp. 264-271.
	15	Thomas Dean , James Allen , Yiannis Aloimonos, Artificial intelligence: theory and practice, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1995
	16	DEAN, T., AND BODDY, M. 1988. An analysis of time-independent planning. In Proceedings of the 7th National Conference on Artificial Intelligence (,4A,41-88) (St. Paul, Minn.). Morgan-Kaufmann, San Marco, Calif., pp. 49-54.
	17	DECHTER, R. 1992. Constraint networks. In Encyclopedia of Artificial Intelligence. John Wiley & Sons, New York, pp. 276-285.
	18	Rina Dechter , Judea Pearl, Structure identification in relational data, Artificial Intelligence, v.58 n.1-3, p.237-270, Dec. 1992 [doi>10.1016/0004-3702(92)90009-M]
	19	DEL VAL, A, 1995. An analysis of approximate knowledge compilation. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI-95) (Montreal, Que., Canada). Morgan-Kaufmann, San Mateo, Calif., pp. 830-836.
	20	DON1NI, F. M., LENZERINI, M., NARDI, D., AND NuTr, W. 1991. The complexity of concept languages. In Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR-91) (Cambridge, Mass.). Morgan-Kaufmann, San Mateo, Calif., pp. 151-162.
	21	DOWLINO, W. F., AND GALLIER, J.H. 1984. Linear time algorithms for testing the satisfiability of propositional Horn formula. J. Log. Prog. 3, 267-284.
	22	Jon Doyle , Ramesh S. Patil, Two theses of knowledge representation: language restrictions, taxonomic classification, and the utility of representation services, Artificial Intelligence, v.48 n.3, p.261-297, April 1991 [doi>10.1016/0004-3702(91)90029-J]
	23	DUBOIS, O., ANDRE, P., BOUFKHAD, Y., AND eARLIER, J. 1995. SAT versus unSAT. In Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D. S. Johnson and M.A. Trick, eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. AMS Press, Providence, R.I.
	24	ELLMAN, T. 1993. Abstraction via approximate symmetry. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJC,41-93), vol. 2. (Chambery, France). Morgan-Kaufmann, Marco, Calif., pp. 916-921.
	25	EROL, K., NAU, D. S., AND SUBRAHMANIAN, V.S. 1992. On the complexity of domain-independent planning. In Proceedings of the lOth National Conference on Artificial Intelligence (AA,41-92) (San Jose, Calif.). MIT Press, Cambridge, Mass., pp. 381-386.
	26	ETHERINGTON, D. g., BORGIDA, A., BRACHMAN, R. J., AND KAUTZ, H. 1989. Vivid knowledge and tractable reasoning: Preliminary report. In Proceedings of the l lth International Joint Conference on Artificial Intelligence (1JCAI-89) (Detroit, Mich.). Morgan-Kaufmann, San Marco, Calif., pp. 1146-1152.
	27	FRISCH, A.M. 1985. Using model theory to specify AI programs. In Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJC,41-85) (Los Angeles, Calif.). Morgan- Kaufmann, San Mateo, Calif., pp. 148-154.
	28	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	29	H. Gelernter, Realization of a geometry-theorem proving machine, Computers & thought, MIT Press, Cambridge, MA, 1995
	30	Goran Gogic , Christos H. Papadimitriou , Martha Sideri, Incremental recompilation of knowledge (extended abstract), Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.922-927, October 1994, Seattle, Washington, United States
	31	GREINER, R., AND SCHUURMANS, D. 1992. Learning useful horn approximations. In Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR-92) (Boston, Mass.). Morgan-Kaufmann, San Mateo, Calif., pp. 383-392.
	32	GUPTA, N., AND NAU, D.S. 1991. Complexity results for blocks-world planning. In Proceedings of the 9th National Conference on Artificial Intelligence (AAAI-91). (Anaheim, Calif.). MIT Press, Cambridge, Mass., pp. 629-635.
	33	Nevin Heintze , Joxan Jaffar, A finite presentation theorem for approximating logic programs, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.197-209, December 1989, San Francisco, California, United States [doi>10.1145/96709.96729]
	34	L. Henschen , L. Wos, Unit Refutations and Horn Sets, Journal of the ACM (JACM), v.21 n.4, p.590-605, Oct. 1974 [doi>10.1145/321850.321857]
	35	HORVITZ, E. J., COOPER, G. F., AND HECKERMAN, D.E. 1989. Reflection and action under scarce resources: Theoretical principles and empirical study. In Proceedings of the llth International Joint Conference on Artificial Intelligence (IJCAI-89) (Detroit, Mich., May). Morgan-Kaufmann, San Marco, Calif., pp. 1121-1126.
	36	IMIELINSKL T. 1987. Domain abstraction and limited reasoning. In Proceedings of the lOth International Joint Conference on Artificial Intelligence (IJCAI-87), vol. 2. Morgan-Kaufmann, San Mateo, Calif., pp. 997-1002.
	37	David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	38	KARP, R. M., ANt) LIPTON, R. 1982. Turing machines that take advice. Enseign. Math., 28, 191-209.
	39	Henry Kautz , Michael Kearns , Bart Selman, Horn approximations of empirical data, Artificial Intelligence, v.74 n.1, p.129-145, March 1995 [doi>10.1016/0004-3702(94)00072-9]
	40	Henry A. Kautz , Bart Selman, A General Framework for Knowledge Compilation, Proceedings of the International Workshop on Processing Declarative Knowledge, p.287-300, July 01-03, 1991
	41	KAuI'z, H., AnD SEL~AN, B. 1992a. Forming concepts for fast inference. In Proceedings of the lOth National Conference on Artificial Intelligence (AAA1-92) (San Jose, Calif.). MIT Press, Cambridge, Mass., pp. 786-793.
	42	Henry Kautz , Bart Selman, Planning as satisfiability, Proceedings of the 10th European conference on Artificial intelligence, p.359-363, August 1992, Vienna, Austria
	43	Henry Kautz , Bart Selman, An empirical evaluation of knowledge compilation by theory approximation, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.155-161, October 1994, Seattle, Washington, United States
	44	Roni Khardon , Dan Roth, Learning to reason, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.682-687, October 1994, Seattle, Washington, United States
	45	K~RKPATmOC, S. AND SELM^~4, B. 1994. Critical behavior in the satisfiability of random Boolean expressions. Science, 264 (May), 1297-1301.
	46	KNOBLOCK, C.A., MINTON, S., AND ETZIONI, O. 1991. Integrating abstraction and explanationbased learning in prodigy. In Proceedings of the 9th National Conference on Artificial Intelligence (A,4A1-91) (Anaheim, Calif.). MIT Press, Cambridge, Mass., pp. 541-546.
	47	KNOBLOCK, C. A., TENENBERG, J. D., AND YANG, Q. 1991. Characterizing abstraction hierarchies for planning. In Proceedings of the 9th National Conference on Artificial Intelligence (AA,41-91) (Anaheim, Calif.). MIT Press, Cambridge, Mass., pp. 692-697.
	48	LARRABEE, T. 1992. Test pattern generation using Boolean satisfiability. IEEE Trans. Comput. Aid. Des. 11, 4-15.
	49	Char-Tung Lee, A completeness theorem and a computer program for finding theorems derivable from given axioms, 1967
	50	LEVESQtJE, H.J. 1984. A logic of implicit and explicit belief. In Proceedings of the 4th National Conference on Artificial Intelligence (,4,4,41-84). (Austin, Tex.). Morgan-Kaufmann, San Mateo, Calif., pp. 198-202.
	51	H J Levesque, Making believers out of computers, Artificial Intelligence, v.30 n.1, p.81-108, Oct. 1986 [doi>10.1016/0004-3702(86)90068-8]
	52	LEVESQUE, H. J., AND BRACHMAN, R.J. 1985. A fundamental tradeoff in knowledge representation and reasoning (revised version). In Readings in Knowledge Representation, R. J. Brachman and H. J. Levesque, eds. Morgan-Kaufmann, San Mateo, Calif., pp. 41-70.
	53	Harry R. Lewis, Renaming a Set of Clauses as a Horn Set, Journal of the ACM (JACM), v.25 n.1, p.134-135, Jan. 1978 [doi>10.1145/322047.322059]
	54	David A. McAllester , Robert Givan, Natural language syntax and first-order inference, Artificial Intelligence, v.56 n.1, p.1-20, July 1992 [doi>10.1016/0004-3702(92)90063-4]
	55	MITCHELL, D., SELMA/q, B., AND LEVESQUE, H. 1992. Hard and easy distribution of SAT problems. In Proceedings of the lOth National Conference on Artificial Intelligence (A,4AI-92) (San lose, Calif.). MIT Press, Cambridge, Mass., pp. 459-465.
	56	MUGGLETON, S., riND BUNTIN~, W. 1988. Machine invention of first-order predicates by inverting resolution. In Proceedings of the 5th International Conference on Machine Learning. Morgan- Kaufmann, San Mateo, Calif., pp 339-344.
	57	PATEL-ScH/qEIDER, P.F. 1986. A four-valued semantics for frame-based description languages. In Proceedings of the 5th National Conference on Artificial Intelligence (AA,41-86) (Philadelphia, Pa.). Morgan-Kaufmann, San Mateo, Calif., pp. 344-348.
	58	PLAISTED, D. 1981. Theorem proving with abstraction. Artif. Int. 16, 47-65.
	59	REITER, R., AND DE KLEER, J. 1987. Foundations of assumption based truth maintenance systems: Preliminary report. In Proceedings of the 6th National Conference on Artificial Intelligence (AAAI-87) (Austin, Tex.). Morgan-Kaufmann, San Mateo, Calif., pp. 183-187.
	60	R. Reiter , A. K. Mackworth, A logical framework for depiction and image interpretation, Artificial Intelligence, v.41 n.2, p.125-155, Dec. 1989 [doi>10.1016/0004-3702(89)90008-8]
	61	SACEV, DOTi, E.D. 1974. Planning in a hierarchy of abstraction spaces. Artif. Int. 5, 2, 115-135.
	62	SCHOPPERS, M.J. 1987. Universal plans for reactive robots in unpredictable environments. In Proceedings of the lOth International Joint Conference on Artificial Intelligence (IJCAI-87) (Milan, Italy). Morgan-Kaufmann, San Mateo, Calif., pp. 1039-1046.
	63	Bart Selman, Tractable default reasoning, University of Toronto, Toronto, Ont., Canada, 1992
	64	SELMAN, B. 1994. Near-Optimal Plans, Tractability, and Reactivity. In Proceedings of the 4th International Conference on Knowledge Representation and Reasoning (KR-94) (Bonn, Germany). Morgan-Kaufmann, San Mateo, Calif., pp. 521-529.
	65	SELMA/q, B., AND KAUTZ, H. 1991. Knowledge compilation using Horn approximations. In Proceedings of the 9th National Conference on Artificial Intelligence (AAAI-91) (Anaheim, Calif.). MIT Press, Cambridge, Mass., pp. 904-909.
	66	SELMA~, B., AND KAUTZ, H. 1993. Domain-independent extensions to GSAT: Solving large structured satisfiability problems. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI-93) (Chambery, France). Morgan-Kaufmann, San Mateo, Calif., pp. 290-295.
	67	SELMA/q, B., AND KIRKPATRICK, S. 1996. Critical behavior in the computational cost of satisfiability testing. Artif Int., 81, in press.
	68	SELMAN, B., AND LEVESQUE, H.J. 1990. Abductive and default reasoning: a computational Core. In Proceedings of the 8th National Conference on Artificial Intelligence (AAAI-90) (Cambridge, Mass.). MIT Press, Cambridge, Mass., pp. 343-348.
	69	Bart Selman , Hector J. Levesque, Support set selection for abductive and default reasoning, Artificial Intelligence, v.82 n.1-2, p.259-272, April 1996 [doi>10.1016/0004-3702(94)00069-7]
	70	SELMAN, B., LEVESQUE, H. J., AND MITCHELL, D. 1992. A new method for solving hard satisfiability problems. In Proceedings of the lOth National Conference on Artificial Intelligence (AAdl-92) (San Jose, Calif.). MIT Press, Cambridge, Mass. pp. 440-446.
	71	Bart Selman , David G. Mitchell , Hector J. Levesque, Generating hard satisfiability problems, Artificial Intelligence, v.81 n.1-2, p.17-29, March 1996 [doi>10.1016/0004-3702(95)00045-3]
	72	SUBRAMANIAN, D., AND GENESERETH, M.R. 1987. The relevance of irrelevance. In Proceedings of the lOth International Joint Conference on Artificial Intelligence (IJCAI-87) (Milan, Italy). Morgan- Kaufmann, San Mateo, Calif., pp. 416-422.
	73	TSEITIN, G.S. 1968. On the complexity of derivation in propositional calculus. Studies in Constructive Mathematics and Mathematical Logic, Part H. A. O. Slisenko, ed. pp. 115-125.
	74	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	75	L. G. Valiant , V. V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science, v.47 n.1, p.85-93, Nov. 1986

CITED BY 61

	Marco Cadoli , Toni Mancini, Knowledge compilation = query rewriting + view synthesis, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Toshihide Ibaraki , Alexander Kogan , Kazuhisa Makino, On functional dependencies in q-Horn theories, Artificial Intelligence, v.131 n.1-2, p.171-187, September 2001
	Roni Khardon, Learning first order universal Horn expressions, Proceedings of the eleventh annual conference on Computational learning theory, p.154-165, July 24-26, 1998, Madison, Wisconsin, United States
	Russell Greiner , Christian Darken , N. Iwan Santoso, Efficient reasoning, ACM Computing Surveys (CSUR), v.33 n.1, p.1-30, March 2001
	Paolo Liberatore, Monotonic reductions, representative equivalence, and compilation of intractable problems, Journal of the ACM (JACM), v.48 n.6, p.1091-1125, November 2001
	Jérôme Amilhastre , Hélène Fargier , Pierre Marquis, Consistency restoriation and explanations in dynamic CSPs----application to configuration, Artificial Intelligence, v.135 n.1-2, p.199-234, 02/01/2002
	Roni Khardon , Dan Roth, Learning to reason, Journal of the ACM (JACM), v.44 n.5, p.697-725, Sept. 1997
	Adnan Darwiche, Decomposable negation normal form, Journal of the ACM (JACM), v.48 n.4, p.608-647, July 2001
	Henry Kautz , Bart Selman, Encoding domain knowledge for prositional planning, Logic-based artificial intelligence, Kluwer Academic Publishers, Norwell, MA, 2000
	Salem Benferhat , Souhila Kaci, Logical representation and fusion of prioritized information based on guaranteed possibility measures: application to the distance-based merging of classical bases, Artificial Intelligence, v.148 n.1-2, p.291-333, August 2003
	Marco Cadoli , Francesco M. Donini , Paolo Liberatore , Marco Schaerf, Preprocessing of intractable problems, Information and Computation, v.176 n.2, p.89-120, 01 August 2002
	Adnan Darwiche , Pierre Marquis, Compiling propositional weighted bases, Artificial Intelligence, v.157 n.1-2, p.81-113, August 2004
	Michèle Sebag , Céline Rouveirol, Resource-bounded Relational Reasoning: Induction and Deduction Through Stochastic Matching, Machine Learning, v.38 n.1-2, p.41-62, Jan.&slash;Feb. 2000
	Roni Khardon , Dan Roth, Learning to Reason with a Restricted View, Machine Learning, v.35 n.2, p.95-116, May 1999
	Roni Khardon, Learning Function-Free Horn Expressions, Machine Learning, v.37 n.3, p.241-275, Dec. 1999
	Marco Cadoli , Thomas Eiter , Georg Gottlob, Complexity of propositional nested circumscription and nested abnormality theories, ACM Transactions on Computational Logic (TOCL), v.6 n.2, p.232-272, April 2005
	Thomas Ellman , Fausto Giunchiglia, Introduction to the special volume on reformulation, Artificial Intelligence, v.162 n.1-2, p.3-5, February 2005
	Alvaro del Val, First order LUB approximations: characterization and algorithms, Artificial Intelligence, v.162 n.1-2, p.7-48, February 2005
	Marcelo Finger , Renata Wassermann, The universe of propositional approximations, Theoretical Computer Science, v.355 n.2, p.153-166, 11 April 2006
	Marta Arias , Aaron Feigelson , Roni Khardon , Rocco A. Servedio, Polynomial certificates for propositional classes, Information and Computation, v.204 n.5, p.816-834, May 2006
	Marcin Dziubiński , Rineke Verbrugge , Barbara Dunin-Kȩplicz, Complexity Issues in Multiagent Logics, Fundamenta Informaticae, v.75 n.1-4, p.239-262, January 2007
	Paolo Liberatore , Marco Schaerf, Compilability of propositional abduction, ACM Transactions on Computational Logic (TOCL), v.8 n.1, p.2-es, January 2007
	Gustav Nordh , Bruno Zanuttini, What makes propositional abduction tractable, Artificial Intelligence, v.172 n.10, p.1245-1284, June, 2008
	Marco Cadoli , Luigi Palopoli , Francesco Scarcello, Propositional lower bounds: Algorithms and complexity, Annals of Mathematics and Artificial Intelligence, v.27 n.1-4, p.129-148, 1999
	Bart Selman, Compute-intensive methods in artificial intelligence, Annals of Mathematics and Artificial Intelligence, v.28 n.1-4, p.35-38, 2000
	Marco Cadoli , Francesco M. Donini, A survey on knowledge compilation, AI Communications, v.10 n.3,4, p.137-150, December 1997
	Sylvie Coste-Marquis , Pierre Marquis, On Stratified Belief Base Compilation, Annals of Mathematics and Artificial Intelligence, v.42 n.4, p.399-442, December 2004
	Pierre Marquis , Nadège Porquet, Resource-Bounded Paraconsistent Inference, Annals of Mathematics and Artificial Intelligence, v.39 n.4, p.349-384, December 2003
	Fabio Massacci , Laura Marraro, Logical Cryptanalysis as a SAT Problem, Journal of Automated Reasoning, v.24 n.1-2, p.165-203, February 2000
	A. K. Shiny , Arun K. Pujari, An Efficient Algorithm to Generate Prime Implicants, Journal of Automated Reasoning, v.22 n.2, p.149-170, February 1999
	Omid Jalali , Tim Menzies , Martin Feather, Optimizing requirements decisions with keys, Proceedings of the 4th international workshop on Predictor models in software engineering, May 12-13, 2008, Leipzig, Germany
	Ken Samuel , Leo Obrst , Suzette Stoutenberg , Karen Fox , Paul Franklin , Adrian Johnson , Ken Laskey , Deborah Nichols , Steve Lopez , Jason Peterson, Translating owl and semantic web rules into prolog: Moving toward description logic programs, Theory and Practice of Logic Programming, v.8 n.3, p.301-322, May 2008
	Frédéric Koriche, Learning to assign degrees of belief in relational domains, Machine Learning, v.73 n.1, p.25-53, October 2008
	S. S. Durbha , R. L. King , V. P. Shah , N. H. Younan, A framework for semantic reconciliation of disparate earth observation thematic data, Computers & Geosciences, v.35 n.4, p.761-773, April, 2009
	Sylvie Coste-Marquis , Daniel Le Berre , Florian Letombe , Pierre Marquis, Propositional fragments for knowledge compilation and quantified boolean formulae, Proceedings of the 20th national conference on Artificial intelligence, p.288-293, July 09-13, 2005, Pittsburgh, Pennsylvania
	Neil Kettle , Andy King, Bit-precise reasoning with affine functions, Proceedings of the Joint Workshops of the 6th International Workshop on Satisfiability Modulo Theories and 1st International Workshop on Bit-Precise Reasoning, July 07-14, 2008, Princeton, New Jersey
	Barry O'Sullivan , Gregory M. Provan, Approximate compilation for embedded model-based reasoning, Proceedings of the 21st national conference on Artificial intelligence, p.894-899, July 16-20, 2006, Boston, Massachusetts
	Yolifé Arvelo , Blai Bonet , María Esther Vidal, Compilation of query-rewriting problems into tractable fragments of propositional logic, Proceedings of the 21st national conference on Artificial intelligence, p.225-230, July 16-20, 2006, Boston, Massachusetts
	Hélène Fargier , Pierre Marquis, Extending the Knowledge Compilation Map: Closure Principles, Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, p.50-54, June 27, 2008
	Thomas Eiter , Kazuhisa Makino, New Results for Horn Cores and Envelopes of Horn Disjunctions, Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, p.60-64, June 27, 2008
	Klaus Lüttich, Approximation of Ontologies in CASL, Proceeding of the 2006 conference on Formal Ontology in Information Systems: Proceedings of the Fourth International Conference (FOIS 2006), p.335-346, May 31, 2006
	Jinbo Huang , Adnan Darwiche, The language of search, Journal of Artificial Intelligence Research, v.29 n.1, p.191-219, May 2007
	Marco Cadoli , Francesco M. Donini , Paolo Liberatore , Marco Schaerf, Space efficiency of propositional knowledge representation formalisms, Journal of Artificial Intelligence Research, v.13 n.1, p.1-31, August 2000
	Yongmei Liu , Gerhard Lakemeyer, On the expressiveness of Levesque's normal form, Journal of Artificial Intelligence Research, v.31 n.1, p.259-272, January 2008
	Knot Pipatsrisawat , Adnan Darwiche, New compilation languages based on structured decomposability, Proceedings of the 23rd national conference on Artificial intelligence, p.517-522, July 13-17, 2008, Chicago, Illinois
	Robert Mateescu , Rina Dechter , Radu Marinescu, AND/OR multi-valued decision diagrams (AOMDDs) for graphical models, Journal of Artificial Intelligence Research, v.33 n.1, p.465-519, September 2008
	Goran Gogic , Christos H. Papadimitriou , Martha Sideri, Incremental recompilation of knowledge, Journal of Artificial Intelligence Research, v.8 n.1, p.23-37, January 1998
	Hélène Fargier , Pierre Marquis, Extending the knowledge compilation map: Krom, Horn, affine and beyond, Proceedings of the 23rd national conference on Artificial intelligence, p.442-447, July 13-17, 2008, Chicago, Illinois
	Adnan Darwiche , Pierre Marquis, A knowledge compilation map, Journal of Artificial Intelligence Research, v.17 n.1, p.229-264, July 2002
	Bart Selman, Stochastic search and phase transitions: AI meets physics, Proceedings of the 14th international joint conference on Artificial intelligence, p.998-1002, August 20-25, 1995, Montreal, Quebec, Canada
	Adnan Darwiche, Compiling knowledge into decomposable negation normal form, Proceedings of the 16th international joint conference on Artifical intelligence, p.284-289, July 31-August 06, 1999, Stockholm, Sweden
	Yacine Boufkhad , Eric Gregoire , Pierre Marquis , Bertrand Mazure , Lakhdar Sais, Tractable cover compilations, Proceedings of the 15th international joint conference on Artifical intelligence, p.122-127, August 23-29, 1997, Nagoya, Japan
	Jussi Rintanen , Alban Grastien, Diagnosability testing with satisfiability algorithms, Proceedings of the 20th international joint conference on Artifical intelligence, p.532-537, January 06-12, 2007, Hyderabad, India
	Goran Gogic , Henry Kautz , Christos Papadimitriou , Bart Selman, The comparative linguistics of knowledge representation, Proceedings of the 14th international joint conference on Artificial intelligence, p.862-869, August 20-25, 1995, Montreal, Quebec, Canada
	Salem Benferhat , Safa Yahi , Habiba Drias, On the compilation of stratified belief bases under linear and possibilistic logic policies, Proceedings of the 20th international joint conference on Artifical intelligence, p.2425-2430, January 06-12, 2007, Hyderabad, India
	Jeff Z. Pan , Edward Thomas, Approximating OWL-DL ontologies, Proceedings of the 22nd national conference on Artificial intelligence, p.1434-1439, July 22-26, 2007, Vancouver, British Columbia, Canada
	Patrick Doherty , Witold Łukaszewicz , Andrzej Szałas, Computing strongest necessary and weakest sufficient conditions of first-order formulas, Proceedings of the 17th international joint conference on Artificial intelligence, p.145-151, August 04-10, 2001, Seattle, WA, USA
	Adnan Darwiche , Pierre Marquis, A perspective on knowledge compilation, Proceedings of the 17th international joint conference on Artificial intelligence, p.175-182, August 04-10, 2001, Seattle, WA, USA
	Pierre Marquis , Nadège Porquet, Resource-bounded inference from inconsistent belief bases, Proceedings of the 17th international joint conference on Artificial intelligence, p.103-108, August 04-10, 2001, Seattle, WA, USA
	Laurent Simon, Efficient consequence finding, Proceedings of the 17th international joint conference on Artificial intelligence, p.359-365, August 04-10, 2001, Seattle, WA, USA
	Jinbo Huang , Adnan Darwiche, DPLL with a trace: from SAT to knowledge compilation, Proceedings of the 19th international joint conference on Artificial intelligence, p.156-162, July 30-August 05, 2005, Edinburgh, Scotland