Efficient reasoning

ABSTRACT

Many tasks require “reasoning”—i.e., deriving conclusions from a corpus of explicitly stored information—to solve their range of problems. An ideal reasoning system would produce all-and-only the correct answers to every possible query, produce answers that are as specific as possible, be expressive enough to permit any possible fact to be stored and any possible query to be asked, and be (time) efficient. Unfortunately, this is provably impossible: as correct and precise systems become more expressive, they can become increasingly inefficient, or even undecidable. This survey first formalizes these hardness results, in the context of both logic- and probability-based reasoning, then overviews the techniques now used to address, or at least side-step, this dilemma.

REFERENCES

• 1: AAAI. 1992. Workshop on Approximation and Abstraction of Computational Theories. Tech. Rep., AAAI.
• 2: Ashraf M. Abdelbar , Sandra M. Hedetniemi, Approximating MAPs for belief networks is NP-hard and other theorems, Artificial Intelligence, v.102 n.1, p.21-38, June 1998 [doi>10.1016/S0004-3702(98)00043-5]
• 3: ALCHOURR ON, C. E., G ARDENFORS,P.,AND MAKIN- SON, D. 1985. On the logic of theory change: partial meet contraction and revision functions. Journal of Symbolic Logic 50, 510- 30.
• 4: ANDERSEN, S. K., OLESEN,K.G.,JENSEN,F.V.,AND JENSEN, F. 1989. HUGIN-a shell for building Bayesian belief universes for expert systems. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89), Detroit, Michigan, Aug. 1989. Morgan Kaufmann, San Mateo, CA, vol. 2, 1080- 1085.
• 5: Stefan Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded, decomposability—a survey, BIT, v.25 n.1, p.2-23, 1985
• 6: AZEVEDO, P. J. 1997. Magic sets with full sharing. Journal of Logic Programming 30, 3 (March), 223-237.
• 7: Fahiem Bacchus , Adam J. Grove , Joseph Y. Halpern , Daphne Koller, From statistical knowledge bases to degrees of belief, Artificial Intelligence, v.87 n.1-2, p.75-143, Nov. 1996 [doi>10.1016/S0004-3702(96)00003-3]
• 8: Virginia E. Barker , Dennis E. O'Connor , Judith Bachant , Elliot Soloway, Expert systems for configuration at Digital: XCON and beyond, Communications of the ACM, v.32 n.3, p.298-318, March 1989 [doi>10.1145/62065.62067]
• 9: BEINLICH, I. A., SUERMONDT,H.J.,CHAVEZ,R.M.,AND COOPER, G. F. 1989. The ALARM monitoring system: a case study with two probabilistic inference techniques for belief networks. In Proceedings of the Second European Conference on Artificial Intelligence in Medicine, London, Aug. 1989. Springer, Berlin.
• 10: BOBROW. 1980. Artificial intelligence. Special Issue on Non-Monotonic Logic.
• 11: BOROS, E., CRAMA,Y.,AND HAMMER, P. 1990. Polynomial-time inference of all valid implications for horn and related formulae. Annals of Mathematics and Artificial Intelligence 1, 21- 32.
• 12: BRACEWELL, R. N. 1978. The Fourier Transform and Its Applications. McGraw-Hill, New York.
• 13: Lee Brownston , Robert Farrell , Elaine Kant , Nancy Martin, Programming expert systems in OPS5: an introduction to rule-based programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 14: Chin-Liang Chang , Richard C. Lee , Richard Char-Tung Lee, Symbolic Logic and Mechanical Theorem Proving, Academic Press, Inc., Orlando, FL, 1997
• 15: Eugene Charniak, Bayesian networks without tears: making Bayesian networks more accessible to the probabilistically unsophisticated, AI Magazine, v.12 n.4, p.50-63, Winter 1991
• 16: CHAUDHRI,V.AND GREINER, R. 1992. A formal analysis of solution caching. In Proceedings of the Ninth Canadian Conference on Artificial Intelligence, Vancouver, 1992.
• 17: CHOW,C.K.AND LUI, C. N. 1968. Aproximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory 14, 3, 462-467.
• 18: CLARK, K. 1978. Negation as failure. In Logic and Data Bases, H. Gallaire and J. Minker Eds. Plenum Press, New York, 293-322.
• 19: W F. Clocksin , Christopher S. Mellish, Programming in Prolog (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1984
• 20: Gregory F. Cooper, The computational complexity of probabilistic inference using Bayesian belief networks (research note), Artificial Intelligence, v.42 n.2-3, p.393-405, March 1990 [doi>10.1016/0004-3702(90)90060-D]
• 21: COUSINS, S., CHEN,W.,AND FRISSE, M. 1993. A tutorial introduction to stochastic simulation algorithms for belief networks. Artificial Intelligence in Medicine 5, 315-340.
• 22: Paul Dagum , Michael Luby, Approximating probabilistic inference in Bayesian belief networks is NP-hard, Artificial Intelligence, v.60 n.1, p.141-153, March 1993 [doi>10.1016/0004-3702(93)90036-B]
• 23: Paul Dagum , Michael Luby, An optimal approximation algorithm for Bayesian inference, Artificial Intelligence, v.93 n.1-2, p.1-27, June 1997 [doi>10.1016/S0004-3702(97)00013-1]
• 24: DALAL,M.AND ETHERINGTON, D. W. 1992a. Tractable approximate deduction using limited vocabulary. In Proceedings of the Ninth Canadian Conference on Artificial Intelligence, Vancouver, May 1992.
• 25: Mukesh Dalal , David W. Etherington, A hierarchy of tractable satisfiability problems, Information Processing Letters, v.44 n.4, p.173-180, Dec. 10, 1992 [doi>10.1016/0020-0190(92)90081-6]
• 26: DARWICHE,A.AND PROVAN, G. M. 1996. Query dags: a practical paradigm for implementing belief network inference. In Proc. Uncertainty in AI.
• 27: DARWICHE,A.AND PROVAN, G. M. 1997. A standard approach for optimizing belief network inference using query dags. In Proc. Uncertainty in AI.
• 28: DECHTER, R. 1996. Topological parameters for timespace tradeoff. In Proc. Uncertainty in AI, San Francisco, 1996, E. Horvitz and F. Jensen, Eds. Morgan Kaufmann, San Maeto, CA, 220- 227.
• 29: R. Dechter, Bucket elimination: a unifying framework for probabilistic inference, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 30: DECHTER,R.AND RISH, I. 1997. A scheme for approximating probabilistic inference. In Proc. Uncertainty in AI.
• 31: DELCHER, A. L., GROVE, A., KASIF,S.,AND PEARL, J. 1996. Logarithmic-time updates and queries in probabilistic networks. J. Artificial Intelligence Research 4, 37-59.
• 32: Werner Nutt , Francesco M. Donini , Maurizio Lenzerini , Daniele Nardi, The complexity of concept languages, Information and Computation, v.134 n.1, p.1-58, April 10, 1997 [doi>10.1006/inco.1997.2625]
• 33: DOWLING,W.F.AND GALLIER, J. H. 1984. Linear time algorithms for testing the satisfiability of propositional horn formula. Journal of Logic Programming 3, 267-84.
• 34: 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]
• 35: DRAPER,D.L.AND HANKS, S. 1994. Localized partial evaluation of belief networks. In Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence, San Francisco, CA, USA, July 1994, R. L. DE MANTARAS AND D. POOLE, Eds. Morgan Kaufmann, San Maeto, CA, 170- 177.
• 36: ELLMAN, T. 1993. Abstraction via approximate symmetry. In IJCAI-93.
• 37: ENDERTON, H. B. 1972. AMathematical Introduction to Logic. Academic Press, New York.
• 38: FELLER, W. 1966. An Introduction to Probability Theory and Its Applications II. John Wiley, New York.
• 39: Nicholas V. Findler, Associative Networks: The Representation and Use of Knowledge by Computers, Academic Press, Inc., Orlando, FL, 1979
• 40: Eugene C. Freuder, Principles and Practice of Constraint Programming-CP '96: Second International Conference, CP 96, Cambridge, Ma, U. S. A., August 1996: Proceedings, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 41: Nir Friedman , Dan Geiger , Moises Goldszmidt, Bayesian Network Classifiers, Machine Learning, v.29 n.2-3, p.131-163, Nov./Dec. 1997 [doi>10.1023/A:1007465528199]
• 42: 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
• 43: Michael R. Genesereth , Nils J. Nilsson, Logical foundations of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 44: GENESERETH,M.R.AND FIKES, R. E. 1992. Knowledge Interchange Format, Version 3.0 Reference Manual. Tech. Rep. Logic-92-1 (June), Computer Science Dept., Stanford Univ.
• 45: Zoubin Ghahramani , Michael I. Jordan, Factorial Hidden Markov Models, Machine Learning, v.29 n.2-3, p.245-273, Nov./Dec. 1997 [doi>10.1023/A:1007425814087]
• 46: Matthew L. Ginsberg, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 47: GINSBERG, M. L. 1991. Knowledge Interchange Format: The KIF of Death. Tech. Rep., Stanford Univ.
• 48: Jonathan Gratch , Gerald DeJong, A statistical approach to adaptive problem solving, Artificial Intelligence, v.88 n.1-2, p.101-142, Dec. 1996 [doi>10.1016/S0004-3702(96)00011-2]
• 49: Russell Greiner, Finding optimal derivation in redundant knowledge bases, Artificial Intelligence, v.50 n.1, p.95-115, June 1991 [doi>10.1016/0004-3702(91)90092-X]
• 50: Russell Greiner, PALO: a probabilistic hill-climbing algorithm, Artificial Intelligence, v.84 n.1-2, p.177-208, July 1996 [doi>10.1016/0004-3702(95)00040-2]
• 51: GREINER, R. 1999. Explanation-based learning. In The Encyclopedia of Cognitive Science,R.WILSON AND F. KEIL, Eds. MIT Press, Cambridge, MA, 301-303. A Bradford Book.
• 52: GREINER,R.AND ELKAN, C. 1991. Measuring and improving the efiectiveness of representations. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, Sydney, Australia, Aug. 1991, 518-524.
• 53: GREINER,R.AND SCHUURMANS, D. 1992. Learning useful horn approximations. In Proceedings of KR-92, San Mateo, CA, Oct. 1992, B. NEBEL, C. RICH, AND W. SWARTOUT, Eds. Morgan Kaufmann, San Mateo, CA.
• 54: GREINER, R., GROVE, A., AND SCHUURMANS, D. 1997. Learning Bayesian nets that perform well. In Uncertainty in Artificial Intelligence.
• 55: Joseph Y. Halpern, An analysis of first-order logics of probability, Artificial Intelligence, v.46 n.3, p.311-350, Dec. 1990 [doi>10.1016/0004-3702(90)90019-V]
• 56: David E. Heckermann, Probabilistic similarity networks, MIT Press, Cambridge, MA, 1991
• 57: HECKERMAN, D. E. 1995. A Tutorial on Learning with Bayesian Networks. Tech. Rep. MSR-TR- 95-06, Microsoft Research.
• 58: HERSKOVITS,E.H.AND COOPER, C. 1991. Algorithms for Bayesian Belief-network Precomputation. In Methods of Information in Medicine.
• 59: HOOS,H.H.AND STUTZLE, T. 1998. Evaluating las vegas algorithms-pitfalls and remedies. In Proc. Uncertainty in AI, San Francisco, 1998. Morgan Kaufmann, San Mateo, CA.
• 60: HORVITZ,E.J.,SUERMONDT,H.J.,AND COOPER,G.F. 1989. Bounded conditioning: flexible inference for decisions under scarce resources. In Proceedings of the Fifth Conference on Uncertainty in Artificial Intelligence (UAI-89), Windsor, Ontario, 1989. Morgan Kaufmann, San Mateo, CA, 182- 193.
• 61: JAAKKOLA,T.S.AND JORDAN, M. I. 1996a. Computing upper and lower bounds on likelihoods in intractable networks. In Proc. Uncertainty in AI.
• 62: JAAKKOLA,T.S.AND JORDAN, M. I. 1996b. Recursive algorithms for approximating probabilities in graphical models. Tech. Rep. 9604 (June), MIT Computational Cognitive Science.
• 63: JENSEN,F.V.,LAURITZEN,S.L.,AND OLESEN, K. G. 1990. Bayesian updating in causal probabilistic networks by local computations. SIAM Journal on Computing 4, 269-282.
• 64: KAUTZ,H.AND SELMAN, B. 1996. Pushing the envelope: planning, propositional logic and stochastic search. In Proceedings AAAI96, Menlo Park, Aug. 1996. AAAI Press/MIT Press, Cambridge, MA, 1194-1201.
• 65: KAUTZ, H., KEARNS, M., AND SELMAN, B. 1993. Reasoning with characteristic models. In AAAI-93, 34-39.
• 66: Roni Khardon , Dan Roth, Reasoning with models, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.1148-1153, October 1994, Seattle, Washington, United States
• 67: KJARULFF, U. 1994. Reduction of computational complexity in Bayesian networks through removal of weak dependences. In Uncertainty in Artificial Intelligence: Proceedings of the Tenth Conference, Seattle, WA, 1994, R. L. DE MANTARAS AND D. POOLE, Eds.
• 68: KOLLER,D.AND PFEFFER, A. 1997. Learning probabilities for noisy first-order rules. In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI), Nagoya, Japan, Aug. 1997.
• 69: KOLLER, D., LEVY, A., AND PFEFFER, A. 1997. P- classic: a tractable probabilistic description logic. In Proceedings of the 14th National Conference on Artificial Intelligence (AAAI), Providence, Rhode Island, Aug. 1997.
• 70: Grzegorz Kondrak , Peter van Beek, A theoretical evaluation of selected backtracking algorithms, Artificial Intelligence, v.89 n.1-2, p.365-387, Jan. 1997 [doi>10.1016/S0004-3702(96)00027-6]
• 71: LAURITZEN,S.AND SPIEGELHALTER, D. J. 1988. Local computations with probabilities on graphical structures and their application to expert systems (with discussion). Journal of the Royal Statistical Society series B 50, 157-224. Reprinted in (Shafer and Pearl 1990).
• 72: LEPAR,V.AND SHENOY, P. P. 1998. A comparison of lauritzen-spiegelhalter, hugin, and shenoy-shafer architectures for computing marginals of probability distributions. In Proc. Uncertainty in AI, San Francisco, 1998. Morgan Kaufmann, San Mateo, CA.
• 73: Hector J. Levesque, Foundations of a functional approach to knowledge representation., Artificial Intelligence, v.23 n.2, p.155-212, July 1984 [doi>10.1016/0004-3702(84)90009-2]
• 74: LEVESQUE,H.AND BRACHMAN, R. 1985. A fundamental tradeoff in knowledge representation and reasoning. In Readings in Knowledge Representation, Los Altos, CA, 1985, R. BRACHMAN AND H.
• 75: LEVESQUE, Eds. Morgan Kaufmann, San Mateo, CA. 41-70.
• 76: LI,Z.AND D'AMBROSIO, B. 1994. Efficient inference in bayes nets as a combinatorial optimization problem. International Journal of Approximate Reasoning 11, 1, 55-81.
• 77: Chao-Lin Liu , Michael P. Wellman, On state-space abstraction for anytime evaluation of Bayesian networks, ACM SIGART Bulletin, v.7 n.2, p.50-57, April 1996 [doi>10.1145/242587.242601]
• 78: Wiktor Marek , Miroslaw Truszczyński, Relating autoepistemic and default logics, Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.276-288, December 1989
• 79: David A. McAllester, Ontic: a knowledge representation system for mathematics, MIT Press, Cambridge, MA, 1989
• 80: MCCARTHY, J. 1977. Epistemological problems in artificial intelligence. In Proceedings of the Fifth International Joint Conference on Artificial Intelligence (IJCAI-77), Cambridge, MA, Aug. 1977. IJCAI.
• 81: MCCARTHY, J. 1980. Circumscription-a form of non-monotonic reasoning. Artificial Intelligence 13, 1-2 (April), 27-39.
• 82: William McCune , Larry Wos, Otter - The CADE-13 Competition Incarnations, Journal of Automated Reasoning, v.18 n.2, p.211-220, April 1997 [doi>10.1023/A:1005843632307]
• 83: MENGSHOEL,O.J.AND WILKINS, D. 1997. Abstraction and aggregation in belief networks. In AAAI97 Workshop on Abstractions, Decisions and Uncertainty.
• 84: Tom M. Mitchell , Richard M. Keller , Smadar T. Kedar-Cabelli, Explanation-Based Generalization: A Unifying View, Machine Learning, v.1 n.1, p.47-80 [doi>10.1023/A:1022691120807]
• 85: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 86: MOORE, R. C. 1982. The role of logic in knowledge representation and commonsense reasoning. In Proceedings of the National Conference on Artificial Intelligence, Pittsburgh, PA, Aug. 1982, D. WALTZ, Ed. AAAI Press, Menlo Park, Calif., 428- 433.
• 87: NAGEL,E.AND NEWMAN, J. 1958. G odel's Proof. New York University Press, New York.
• 88: Robert Neches , Richard Fikes , Tim Finin , Tom Gruber , Ramesh Patil , Ted Senator , William R. Swartout, Enabling technology for knowledge sharing, AI Magazine, v.12 n.3, p.36-56, Fall 1991
• 89: Liem Ngo , Peter Haddawy, Probabilistic Logic Programming and Bayesian Networks, Proceedings of the 1995 Asian Computing Science Conference on Algorithms, Concurrency and Knowledge, p.286-300, December 11-13, 1995
• 90: Nils J. Nilsson, Probabilistic logic, Artificial Intelligence, v.28 n.1, p.71-88, Feb. 1986 [doi>10.1016/0004-3702(86)90031-7]
• 91: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 92: Francis Jeffry Pelletier, THINKER, Proceedings of the 8th International Conference on Automated Deduction, p.701-702, July 27-August 01, 1986
• 93: POOLE, D. 1993a. Average-case analysis of a search algorithm for estimating prior probabilities in Bayesian networks with extreme probabilities. In Proceedings IJCAI-93, Chamberery, France, Aug. 1993, 606-612.
• 94: David Poole, Probabilistic Horn abduction and Bayesian networks, Artificial Intelligence, v.64 n.1, p.81-129, Nov. 1993 [doi>10.1016/0004-3702(93)90061-F]
• 95: POOLE, D., GOEBEL, R., AND ALELIUNAS, R. 1987. Theorist: a logical reasoning system for default and diagnosis. In The Knowledge Frontier: Essays in the Representation of Knowledge, New York, 1987, N. CERCONE AND G. MCCALLA, Eds. Springer, Berlin, 331-52.
• 96: David Poole , Alan Mackworth , Randy Goebel, Computational intelligence: a logical approach, Oxford University Press, Oxford, 1997
• 97: PRADHAN,M.AND DAGUM, P. 1996. Optimal Monte Carlo estimation of belief network inference. In Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence (UAI-96), San Francisco, Aug. 1996, E. HORVITZ AND F. J ENSEN, Eds. Morgan Kaufmann, San Mateo, CA. 446- 453.
• 98: PRADHAN, M., PROVAN, G., MIDDLETON,B.,AND HENRION, M. 1994. Knowledge engineering for large belief networks. In Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence, San Francisco, CA, USA, July 1994, R. L. DE MAN- TARAS AND D. POOLE, Eds. Morgan Kaufmann, San Mateo, CA, 484-490.
• 99: RABINER,L.R.AND JUANG, B. H. 1986. An introduction to hidden Markov models. IEEE ASSP Magazine, 4ff.
• 100: REITER, R. 1978a. Deductive question-answering on relational data bases. In Logic and Data Bases, H. GALLAIRE AND J. MINKER, Eds. Plenum Press, New York, 149-177.
• 101: REITER, R. 1978b. On closed world data bases. In Logic and Data Bases,H.GALLAIRE AND J. MINKER Eds. Plenum Press, New York, 55-76.
• 102: Raymond Reiter, Equality and Domain Closure in First-Order Databases, Journal of the ACM (JACM), v.27 n.2, p.235-249, April 1980 [doi>10.1145/322186.322189]
• 103: REITER, R. 1987. Nonmonotonic reasoning. In Annual Review of Computing Sciences, vol. 2, Annual Reviews, Palo Alto, 147-187.
• 104: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• 105: Dan Roth, On the hardness of approximate reasoning, Artificial Intelligence, v.82 n.1-2, p.273-302, April 1996 [doi>10.1016/0004-3702(94)00092-1]
• 106: RUDNICKI, P. 1992. An overview of the Mizar project. In Notes to a Talk at the Workshop on Types for Proofs and Programs.
• 107: SACERDOTI, E. D. 1973. Planning in a hierarchy of abstraction spaces. In IJCAI-73.
• 108: Sumit Sarkar , Ishwar Murthy, Constructing Efficient Belief Network Structures With Expert Provided Information, IEEE Transactions on Knowledge and Data Engineering, v.8 n.1, p.134-143, February 1996 [doi>10.1109/69.485642]
• 109: A. Carlisle Scott , Jan E. Clayton , Elizabeth L. Gibson, A Practical Guide to Knowledge Acquisition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 110: Bart Selman , Henry Kautz, Knowledge compilation and theory approximation, Journal of the ACM (JACM), v.43 n.2, p.193-224, March 1996 [doi>10.1145/226643.226644]
• 111: SELMAN, B., LEVESQUE, H., AND MITCHELL, D. 1992. A new method for solving hard satisfiability problems. In Proceedings of the Twelfth National Conference on Artificial Intelligence, San Jose, July 1992, 440-446.
• 112: Glenn Shafer , Judea Pearl, Readings in uncertain reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 113: SINGH, M. 1998. Learning Belief Networks. Ph.D. thesis, Dept. of Computer Science, Univ. of Pennsylvania.
• 114: David E. Smith , Michael R. Genesereth, Ordering conjunctive queries, Artificial Intelligence, v.26 n.2, p.171-215, May 1985 [doi>10.1016/0004-3702(85)90028-1]
• 115: D E Smith , M R Genesereth , M L Ginsberg, Controlling recursive inference, Artificial Intelligence, v.30 n.3, p.343-390, Dec. 1986 [doi>10.1016/0004-3702(86)90003-2]
• 116: Padhraic Smyth , David Heckerman , Michael I. Jordan, Probabilistic independence networks for hidden Markov probability models, Neural Computation, v.9 n.2, p.227-269, Feb. 15, 1997 [doi>10.1162/neco.1997.9.2.227]
• 117: SRINIVAS, S. 1994. A probabilistic apprach to hierarchical model-based diagnosis. Tech. Rep. Research Rep. no. KSL-94-14 (Feb.), Knowledge Systems Laboratory, Stanford Univ.
• 118: H. Jacques Suermondt , Gregory F. Cooper, Initialization for the method of conditioning in Bayesian belief networks, Artificial Intelligence, v.50 n.1, p.83-94, June 1991 [doi>10.1016/0004-3702(91)90091-W]
• 119: Arun Swami , Anoop Gupta, Optimization of large join queries, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.8-17, June 01-03, 1988, Chicago, Illinois, United States
• 120: Geoffrey G. Towell , Jude W. Shavlik, Extracting Refined Rules from Knowledge-Based Neural Networks, Machine Learning, v.13 n.1, p.71-101, Oct. 1993 [doi>10.1023/A:1022683529158]
• 121: R. Treitel , M. R. Genesereth, Choosing directions for rules, Journal of Automated Reasoning, v.3 n.4, p.395-431, Dec. 1987
• 122: TURING, A. M. 1936. On computable numbers, with an application to the Entscheidungs problem. Proc. London Math. Soc. 2, 42, 230-265. Corrections on vol. 2, 43, 544-546.
• 123: VALIANT, L. G. 1979. The complexity of enumeration and reliability problems. SIAM Journal on Computing 8, 3, 410-421.
• 124: Rick F. van der Lans, The SQL standard: a complete guide reference, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1989
• 125: Robert A. van Engelen, Approximating Bayesian Belief Networks by Arc Removal, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.8, p.916-920, August 1997 [doi>10.1109/34.608295]
• 126: M. P. Wellman, Fundamental concepts of qualitative probabilistic networks, Artificial Intelligence, v.44 n.3, p.257-303, Aug. 1990 [doi>10.1016/0004-3702(90)90026-V]
• 127: WELLMAN, M. 1994. Abstraction in Probabilistic Reasoning. Tech. Rep., Univ. of Michigan. Tutorial prepared for the Summer Institute on Probability in AI, Corvallis, OR, July 1994. See http://ai.eecs.umich.edu/people/wellman/ tut/Abstraction.html.
• 128: Daniel S. Weld , Johan de Kleer, Readings in qualitative reasoning about physical systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 129: Geoffrey I. Webb , Jason Wells , Zijian Zheng, An Experimental Evaluation of Integrating Machine Learning with Knowledge Acquisition, Machine Learning, v.35 n.1, p.5-23, April 1999 [doi>10.1023/A:1007504102006]
• 130: ZHANG,N.L.AND POOLE, D. 1994. A simple approach to Bayesian network computations. In Proc. of the 10th Canadian Conference on Artificial Intelligence, Banff, Alberta, Canada, May 1994.
• 131: Shlomo Zilberstein, Operational Rationality through Compilation of Anytime Algorithms, University of California at Berkeley, Berkeley, CA, 1993
• 132: Shlomo Zilberstein, Resource-bounded reasoning in intelligent systems, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996 [doi>10.1145/242224.242243]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Performance

Keywords:
efficiency trade-offs, soundness/completeness/expressibility