Artificial Intelligence Seminar

Winter 1996

Tractable Approaches to Logical Deduction

Reading List

Revised 96/2/21

The following is a partial list of papers relevant to the topic of tractable methods for deduction. Of course, we will not cover all of this material. Boldfaced entries indicate papers we definitely hope to cover.

1: A.R. Anderson and N.D Belnap. Entailment, the logic of relevance and neccessity. Princeton university press, 1975.
2: M. Boddy and T. Dean. Solving time dependent planning problems. Technical Report CS-89-03, Dept. of Computer Science, Brown University, 1989. [Extended version of their AAAI-89 paper].
3: M. Boddy and T. Dean. Solving time dependent planning problems. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89), pages 979-984, Detroit, Michigan, 1989. [Expectation-driven iterative refinement as an anytime planning technique].
4: A. Borgida and D.W. Etherington. Hierarchical knowledge bases and efficient disjunctive reasoning. In R.J. Brachman, H.J. Levesque, and R. Reiter, editors, Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, pages 33-43, Toronto, Canada, May 1989. Morgan Kaufmann.
5: R.J. Brachman and H.J. Levesque. The tractability of subsumption in frame based description languages. In Proceedings of the National Conference on Artificial Intelligence (AAAI-84), pages 34-37, 1984.
6: T. Bylander. A simple model of knowledge compilation. IEEE Expert, 6:73-74, 1991.
7: M. Cadoli and M. Schaerf. Approximate inference in default logic and circumscription. In Working Notes of the Fourth International Workshop on Nonmonotonic Reasoning, 1992.
8: M. Cadoli and M. Schaerf. Approximation in concept description languages. In B. Nebel, C. Rich, and W. Swartout, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference (KR'92), pages 330-341, Cambridge, Massachusetts, 1992. Morgan Kaufmann Publishers.
9: M. Cadoli and M. Schaerf. Tractable Reasoning via Approximation. In [10], pages 12-15, 1992.
10: J. Crawford, editor. Proceedings of the AAAI Workshop on Tractable Reasoning. American Association for Artificial Intelligence, San Jose, California, 1992.
11: J. Crawford and B. Kuipers. Towards a theory of access-limited logic for knowledge representation. In Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning (KR'89), pages 67-78, 1989.
12: J.M. Crawford. Access-Limited Logic-A Language for Knowledge Representation. PhD thesis, University of Texas at Austin, Austin, Texas, September 1990.
13: J.M. Crawford and B.J. Kuipers. Negation and proof by contradiction in access-limited logic. In Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91), pages 897-903, 1991.
14: M. Dalal and D. W. Etherington. A hierarchy of tractable satisfiability problems. Information Processing Letters, 44(4):173-231, December 1992.
15: M. Dalal and D. W. Etherington. Tractable approximate deduction using limited vocabularies. In Proceedings of the Ninth Canadian Conference on Artificial Intelligence (AI '92), pages 206-212, Vancouver, Canada, 1992.
16: E. Davis. Lucid representations. Technical Report 565, New York University, Dept. of Computer Science, June 1991.
17: Johann de Kleer. An improved incremental algorithm for generating prime implicates. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), pages 780-785, 1992.
18: T. Dean and M. Boddy. An analysis of time dependent planning. In Proceedings of the Seventh National Conference on Artificial Intelligence (AAAI-88), pages 49-54, St. Paul, MN, 1988. [Anytime algorithms].
19: A. del Val. Tractable databases: how to make propositional unit resolution complete through compilation. In Principles of Knowledge Representation and Reasoning: Proceedings of the Fourth International Conference (KR'94), pages 551-561, 1994.
20: A. del Val. An analysis of approximate knowledge compilation. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), 1995.
21: F.M. Donini, M. Lenzerini, D. Nardi, and W. Nutt. Tractable concept languages. In Proceedings of the Twelveth International Joint Conference on Artificial Intelligence (IJCAI-91), pages 458- 463, 1991.
22: W.F. Dowling and J.H. Gallier. Linear-time algorithms for testing the satisfiability of propositional Horn formulae. Journal of Logic Programming, 1(3):267-284, 1984.
23: J. Elgot-Drapkin, M. Miller, and D. Perlis. Life on a desert island: Ongoing work on real-time reasoning. In Proceedings of the 1987 Workshop on the Frame Problem in Artificial Intelligence, pages 349-357, Lawrence, KS, April 1987.
24: D.W. Etherington and J.M. Crawford. Toward efficient default reasoning. In Working Notes of the Fourth International Workshop on Nonmonotonic Reasoning, 1992.
25: D.W. Etherington and J.M. Crawford. Toward efficient default reasoning. In Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI-96), pages 627--632, 1996.
26: R. Fagin and J.Y. Halpern. Belief, awareness and limited reasoning. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI-85), pages 491-501, 1985.
27: A.M. Frisch. Inference without chaining. In Proceedings of the Tenth International Joint Conference on Artificial Intelligence (IJCAI-87), pages 515-519, 1987.
28: G. Gallo and M.G. Scutellà. Polynomially solvable satisfiability problems. Information Processing Letters, 29:221-227, 1988.
29: M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H., NY, 1979.
30: M.L. Ginsberg. The computational value of nonmonotonic reasoning. In Proceedings, Second International Conference on Principles of Knowledge Representation and Reasoning, Cambridge, MA, April 1991. Morgan Kaufmann.
31: G. Gottlob. Complexity results for nonmonotonic logics. In Working Notes of the Fourth International Workshop on Nonmonotonic Reasoning, 1992.
32: J. Hobbs. Granularity. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI-85), pages 432-435, 1985.
33: T. Imielinski. Domain abstraction and limited reasoning. In Proceedings of the Tenth International Joint Conference on Artificial Intelligence (IJCAI-87), pages 997-1003, Milan, 1987.
34: T. Imielinski and M. Dalal. `Your time is up': approximate query answering in deductive databases. In Proceedings of the Workshop on Automatic Generation of Approximations and Abstractions (AGAA-90), pages 175-185, Boston, Massachusetts, 1990. American Association for Artificial Intelligence.
35: T. Imielinski and W. Lipski. Incomplete information in relational databases. Journal of the ACM, 31(4):761-791, 1984.
36: H. Kautz and B. Selman. Hard problems for simple default logics. In Proceedings, First International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Canada, May 1989. Morgan Kaufmann.
37: H. Kautz and B. Selman. A general framework for knowledge compilation. In Proceedings of the International Workshop on Processing Declarative Knowledge (PDK), Kaiserslautern, Germany, 1991.
38: H. Kautz and B. Selman. Forming concepts for fast inference. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), pages 786-793, 1992. [Concept learning to derive compact representations of bounds].
39: H. Kautz and B. Selman. Horn approximations of empirical data. Artificial Intelligence, 1992.
40: H. Kautz and B. Selman. An Empirical Evaluation of Knowledge Compilation. In Proceedings of the Eleventh National Conference on Artificial Intelligence (AAAI-94), 1994.
41: R.M. Keller. Applying knowledge compilation techniques to model-based reasoning. IEEE Expert, 6, 1991.
42: R. Khardon and D. Roth. Reasoning with models. In Proceedings of the Eleventh National Conference on Artificial Intelligence (AAAI-94), 1994.
43: K. Konolige. What awareness isn't: a sentential view of implicit and explicit belief. In Theoretical Aspects of Reasoning About Knowledge, pages 241-250, 1986.
44: G. Lakemeyer and H. J. Levesque. A tractable knowledge representation service with full introspection. In Theoretical Aspects of Reasoning About Knowledge, pages 145-159, 1988.
45: Gerhard Lakemeyer. In Theoretical Aspects of Reasoning About Knowledge, 1986. [First-order version of Levesque's logic of implicit/explicit belief].
46: H.J. Levesque. A Logic of Implicit and Explicit Belief. Proceedings of the National Conference on Artificial Intelligence (AAAI-84), pages 198-202, 1984.
47: H.J. Levesque. A logic for implicit and explicit belief. Technical Report FLAIR TR 32, Fairchild Laboratory for Artificial Intelligence Research, 1984.
48: H.J. Levesque. Making believers out of computers. Artificial Intelligence, 30:81-108, 1986. [Vivid reasoning].
49: H.J. Levesque and R.J. Brachman. A fundamental tradeoff in knowledge representation and reasoning (revised version). In R.J. Brachman and H.J. Levesque, editors, Readings in Knowledge Representation, pages 41-70. Morgan Kaufmann, Los Altos, California, 1985.
50: W. Lipski, Jr. On semantical issues connected with incomplete information databases. ACM Transactions on Database Systems, 4(3), 1979.
51: P. Marquis. Knowledge compilation using theory prime implicates. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), 1995.
52: D.A. McAllester. Automatic recognition of tractability in inference relations. Memo 1215, MIT Artificial Intelligence Laboratory, February 1990. to appear in JACM.
53: Abdel-illa Mouaddib and Shlomo Zilberstein. Knowledge-based anytime computation. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), pages 775-781, 1995. [Granularity to achieve anytime for knowledge bases].
54: P. F. Patel-Schneider. A decidable first-order logic for knowledge representation. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI-85), 1985.
55: P. F. Patel-Schneider. A Decidable First-Order Logic for Knowledge Representation. Journal of Automated Reasoning, 6:361-388, 1990.
56: D. Perlis. Nonmonotonicity and real-time reasoning. In Proceedings of the First International Workshop on Nonmonotonic Reasoning, New Paltz, NY, October 1984.
57: D.A. Plaisted. Theorem proving with abstraction. Artificial Intelligence, 16:47-108, 1981.
58: B. Selman and H. Kautz. Knowledge compilation using Horn approximations. In Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91), pages 904-909, 1991.
59: J. Stillman. It's not my default: the complexity of membership problems in restricted propositional default logics. In Proceedings of the Eight National Conference on Artificial Intelligence (AAAI-90), pages 571-578, 1990.
60: J. Stillman. The complexity of propositional default logics. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), pages 794-799, 1992.
61: P. van Beek. Approximate algorithms for temporal reasoning. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89), pages 1291-1296, Detroit, Michigan, 1989.
62: P. van Beek and Cohen R. Exact and approximate reasoning about temporal relations. Computational Intelligence, 1990.

See the class schedule.

Back to David Etherington's home page.