Proceedings

A Computational Model of Tractable Reasoning - Taking Inspiration from Cognition

Download BibTeX Cite

Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Cognitive Modeling. Pages 202-206.

© 1993 International Joint Conferences on Artificial Intelligence

Abstract

Polynomial time complexity is the usual 'threshold' for distinguishing the tractable from the intractable and it may seem reasonable to adopt this notion of tractability in the context of knowledge representation and reasoning. It is argued that doing so may be inappropriate in the context of common sense reasoning underlying language understanding. A more stringent criteria of tractability is proposed. A result about reasoning that is tractable in this stronger sense is outlined. Some unusual properties of tractable reasoning emerge when the formal specification is grounded in a neurally plausible architecture.

  1. [Ajjanagadde and Shastri, 1991] V.G . Ajjanagadde and L. Shastri. Rules and variables in neural nets. Neural Computation, 3:121-134.
  2. [Brachman and Levesque, 1984] R . Brachman and H. Levesque. The tractability of Subsumption in frame-based description languages. In Proceedings of AAAI-84, the fourth national conference on artificial intelligence. Morgan Kaufman. [Bylander et al., 1991]
  3. T. Bylander, D. Allemang, M. C. Tanner, J . R. Josephson. The computational complexity of abduction. Artificial Intelligence, 47(1- 3), 25-60 .
  4. [Carpenter and Just, 1977] P.A . Carpenter and M.A. Just. Reading Comprehension as Eyes See It. In: Cognitive Processes in Comprehension. [Dietz eta/., 1993]
  5. P. Dietz, D. Krizanc, S. Rajasekaran, L. Shastri. A lower-bound result for the common el- ement problem and its implication for reflexive rea- soning. Forthcoming Technical Report, Department of Computer and Information Science, Univ. of Penn- sylvania.
  6. [Dowling and Gallier, 1984] W .F. Dowling and J .H. Gallier. Linear time algorithm for testing the satisfiability of propositional horn formula. Journal of Logic Programming, 3:267-284.
  7. [Fahlman, 1979] S.E. Fahlman. NETL : A system for representing real-world knowledge, MIT Press.
  8. [Frisch and Allen, 1982] A.M. Frisch and J .F. Allen. Knowledge retrieval as limited inference. In: Notes in Computer Science: 6th Conference on Automated Deduction ed. D. W. Loveland . Springer-Verlag.
  9. [Guha and Lenat, 1990] R.V . Guha and D.B . Lenat . Cyc: A Mid-Term report. AI Magazine, Volume 11, Number 3, 1990.
  10. [Henderson, 1992] J. Henderson. A Connectionist Parser for Structure Unification Grammar. In Proceedings of ACL-92. 206 Cognitive Modeling [Holldobler, 1990]
  11. S. Holldobler. CHCL: A Connection- ist Inference System for Horn Logic based on the Con- nection Method and Using Limited Resources. TR-90- 042, International Computer Science Institute, Berke- ley, CA.
  12. [Kautz and Selman, 1991] H.A. Kautz and B. Selman. Hard problems for Simple Default Logics. Artificial Intelligence, 47(1-3), 243-279.
  13. [Levesque, 1988] H.J . Levesque. Logic and the complex- ity of reasoning. Journal of Philosophical Logic, 17, pp 335-389.
  14. [Mani and Shastri, 1992] D.R. Mani and L. Shastri. A connectionist solution to the multiple instantiation problem using temporal synchrony. In .Proceedings of the Fourteenth Conference of the Cognitive Science Society. Lawrence Erlbaum.
  15. [Mani and Shastri, 1991] D.R. Mani and L. Shastri. Combining a Connectionist Type Hierarchy with a Connectionist Rule-Based Reasoner. In Proceedings of the Thirteenth Conference of the Cognitive Science Society. Lawrence Erlbaum.
  16. [McAllester, 1990] D.A. McAllester. Automatic recogni- tion of tractability in inference relations. Memo 1215, MIT Artificial Intelligence Laboratory, February 1990.
  17. [Miller, 1956] G.A. Miller. The magical number seven, plus or minus two: Some limits on our capacity for processing information . The Psychological Review, 63(2), pp . 81-97.
  18. [Patel-Schneider, 1985] P. Patel-Schneider. A decidable first-order logic for knowledge representation . In Pro- ceedings of IJCAI-85. IJCAI
  19. Morgan Kaufman. [Rajasekaran, 1992]
  20. S. Rajasekaran. Personal communi- cation. [Selman and Levesque, 1989] B. Selman and H.J . Levesque. The tractability of path-based in- heritance. In Proceedings of IJCAI-89. pp. 1140-1145. IJCAI
  21. Morgan Kaufmann. [Shastri, 1992]
  22. L. Shastri. Neurally motivated con- straints on a working memory capacity of a produc- tion system for rapid parallel processing. To appear in the Proceedings of the Fourteenth Conference of the Cognitive Science Society. Lawrence Erlbaum.
  23. [Shastri, 1991] L. Shastri. Why Semantic networks? In Principles of Semantic Networks. Edited by John Sowa. Morgan Kaufman Los Altos.
  24. [Shastri, 1988] L. Shastri. Semantic networks : An ev- idential formulation and its connectionist realization, Pitman London/ Morgan Kaufman Los Altos. 1988.
  25. [Shastri and Ajjanagadde, 1990] L. Shastri and V.G. Ajjanagadde. From Simple Associations to Sys- tematic Reasoning: A connectionist representation of rules, variables and dynamic bindings using temporal synchrony. Technical Report MS-CIS-90-05, Depart- ment of Computer and Information Science, Univ. of Pennsylvania. (Revised January 1992). To appear in Behavioral and Brain Sciences.
  26. [Ullman and van Gelder, 1988] J.D. Ullman and A. van Gelder. Parallel Complexity of Logical Query Pro- grams. Algorithmica, 3, 5-42 .

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards