×

Compiling a default reasoning system into Prolog. (English) Zbl 0713.68017

Summary: Artificial intelligence researchers have been designing representation systems for default and abductive reasoning. Logic Programming researchers have been working on techniques to improve the efficiency of Horn clause deduction systems. This paper describes how one such default and abductive reasoning system (namely Theorist) can be translated into Horn clauses (with negation as failure), so that we can use the clarity of abductive reasoning systems and the efficiency of Horn clause deduction systems. We thus show how advances in expressive power that artificial intelligence workers are working on can directly utilise advances in efficiency that logic programming researchers are working on. An actual code from a running system is given.

MSC:

68N20 Theory of compilers and interpreters
68N17 Logic programming
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brewka, G., ”Tweety–Still Flying: Some Remarks on Abnormal Birds, Applicable Rules and a Default Prover,”Proc. AAAI-86 pp. 8–12.
[2] Chang, C-L. and Lee, R. C-T.,Symbolic Logic and Mechanical Theorem Proving, Academic Press, 1973. · Zbl 0263.68046
[3] Bruynooghe, M. and Pereira, L. M., ”Deductive Revision by Intelligent Backtracking,” inImplementation of Prolog (J. A. Campbell ed.), Ellis Horwood, 1984.
[4] Cox, P. T. and Pietrzykowski, T., ”General Diagnosis by Abductive Inference,”Technical Report, CS8701, School of Computer Science, Technical University of Nova Scotia, April 1987.
[5] Dincbas, M., Simonis, H., and Van Hentenryck, P., ”Solving Large Combinatorial Problems in Logic Programming,”ECRC Technical Report, TR-LP-21, June 1987. · Zbl 0719.68013
[6] Doyle, J., ”A Truth Maintenance System,”Artificial Intelligence, Vol. 12, pp. 231–273, 1979. · doi:10.1016/0004-3702(79)90008-0
[7] de Kleer, J. ”An Assumption-based TMS,”Artificial Intelligence, Vol. 28, No. 2, pp. 127–162, 1986. · doi:10.1016/0004-3702(86)90080-9
[8] de Kleer, J. and Konolige, K., ”Eliminating the Fixed Predicates from a Circumscription,”Artificial Intelligence, Vol. 39, No. 3, pp. 391–398, 1989. · Zbl 0672.03013 · doi:10.1016/0004-3702(89)90018-0
[9] Enderton, H. B.,A Mathematical Introduction to Logic, Academic Press, Orlando, 1972. · Zbl 0298.02002
[10] Etherington, D. W.,Reasoning with Incomplete Information, Morgan Kaufmann, 1988. · Zbl 0694.68003
[11] Genesereth, M. and Nilsson, N.,Logical Foundations of Artificial Intelligence, Morgan-Kaufmann, Los Altos, California, 1987. · Zbl 0645.68104
[12] Ginsberg, M. L., ”A Circumscriptive Theorem Prover,”Artificial Intelligence, Vol. 39, No. 2, pp. 209–230, 1989. · Zbl 0677.68096 · doi:10.1016/0004-3702(89)90026-X
[13] Goebel, R. G. and Goodwin, S. D., ”Applying Theory Formation to the Planning Problem,”Proceedings of the 1987 Workshop on The Frame Problem in Artificial Intelligence (F. M. Brown, ed.), Morgan Kaufmann, pp. 207–232.
[14] Helft, N., Inoue, K., and Poole, D., ”Extracting Answers in Circumscription,”ICOT Technical Memorandum, TM-855, ICOT, 1989. · Zbl 0742.68053
[15] Kowalski, R., ”Algorithm=Logic+Control,”Comm. A.C.M., Vol 22, No 7, pp. 424–436, 1979. · Zbl 0404.68010
[16] Lifschitz, V., ”Computing Circumscription,”Proc. IJCAI85, Morgan Kaufmann, pp. 121–127, 1985.
[17] Lloyd, J.,Foundations of Logic Programming, 2nd Edition, Springer-Verlag, 1987. · Zbl 0668.68004
[18] Loveland, D. W.,Automated Theorem Proving: A Logical Basis, North-Holland, Amsterdam, 1978. · Zbl 0364.68082
[19] Loveland, D. W., ”Near-Horn Logic Programming,”Proc. 6th International Logic Programming Conference, 1987.
[20] McCarthy, J., ”Applications of Circumscription to Formalising Common Sense Knowledge,”Artificial Intelligence, Vol. 28, No. 1, pp. 89–116, 1986. · doi:10.1016/0004-3702(86)90032-9
[21] Meltzer, B., ”The Semantics of Induction and the Possibility of Complete Systems of Inductive Reasoning,”Artificial Intelligence, 1, pp. 189–192, 1970. · Zbl 0206.00902 · doi:10.1016/0004-3702(70)90006-8
[22] Motooka, T., Tanaka, H., Aida, H., Hirata, K., and Maruyama, T., ”The Architecture of a Parallel Inference Engine–PIE,”Proc. Int. Conf. on Fifth Generation Computing Systems, pp. 479–488, 1984.
[23] Naish, L., ”Negation and Quantifiers in NU-PROLOG,”Proc. 3rd Int. Conf. on Logic Programming, Springer-Verlag, pp. 624–634, 1986. · Zbl 0595.68006
[24] Neufeld, E. M. and Poole, D., ”Towards Solving the Multiple Extension Problem: Combining Defaults and Probabilities,”Proc. 3rd AAAI Workshop on Reasoning with Uncertainty, Seattle, pp. 305–312, 1987.
[25] Plaisted, D. A., ”The Occur-check Problem in Prolog,”New Generation Computing, 2, pp. 309–322, 1984. · Zbl 0595.68007 · doi:10.1007/BF03037324
[26] Poole, D. L., ”Making Clausal Theorem Provers Non-clausal,”Proc. CSCSI-84, pp. 124–125, 1984.
[27] Poole, D. and Goebel, R. G., ”On Eliminating Loops in Prolog,”SIGPLAN Notices, Vol 20, No 8, pp. 38–40, August 1985. · doi:10.1145/988346.988350
[28] Poole, D. and Goebel, R., ”Gracefully Adding Negation to Prolog,”Proc. 5th International Logic Programming Conference, London, pp. 635–641, 1986. · Zbl 0608.68074
[29] Poole, D., ”A Logical Framework for Default Reasoning,”Artificial Intelligence, Vol. 36, No. 1, pp. 27–47, 1987. · Zbl 0647.68094 · doi:10.1016/0004-3702(88)90077-X
[30] Poole, D., ”Explanation and Prediction: an Architecture for Default and Abductive Reasoning,”Computational Intelligence, Vol. 5, No. 2, pp. 97–110, 1989. · doi:10.1111/j.1467-8640.1989.tb00319.x
[31] Poole, D., ”A Methodology for Using a Default and Abductive Reasoning System,”International Journal of Intelligent Systems, Vol. 5, No. 2, pp. 521–548, 1990. · Zbl 0714.68091 · doi:10.1002/int.4550050506
[32] Poole, D. L., Goebel, R. G., and Aleliunas, R. ”Theorist: A Logical Reasoning System for Defaults and Diagnosis,” inThe Knowledge Frontier: Essays in the Representation of Knowledge (N. Cercone and G. McCalla, eds.), Springer Varlag, New York, pp. 331–352, 1987.
[33] Pople, H. E., ”On the Mechanization of Abductive Logic,”Proc. IJCAI-73, pp. 147–152, 1973.
[34] Przymusinski, T. C., ”An Algorithm for Computing Circumscription,”Artificial Intelligence, Vol. 38, No. 1, pp. 49–74, 1989. · Zbl 0663.68098 · doi:10.1016/0004-3702(89)90067-2
[35] Reiter, R., ”A Logic for Default Reasoning,”Artificial Intelligence, Vol. 13, pp. 81–132, 1980. · Zbl 0435.68069 · doi:10.1016/0004-3702(80)90014-4
[36] Shapiro, E. Y.,Algorithmic Program Debugging, MIT Press, 1983. · Zbl 0589.68003
[37] Smith, D. and Genesereth, M., ”Ordering Conjunctive Queries,”Artificial Intelligence, Vol. 26, No. 3, pp. 171–215, 1986. · Zbl 0569.68077 · doi:10.1016/0004-3702(85)90028-1
[38] Spencer, E. B., ”Avoiding Redundant Explanations”Proc. NACLP-90, Austin, 1990.
[39] Stickel, M. E., ”A Prolog Technology Theorem Prover,”New Generation Computing, 2, pp. 371–383, 1984. · doi:10.1007/BF03037328
[40] Stickel, M. E., ”A Prolog Technology Theorem Prover: Implementation by an Extended Prolog Compiler,”Journal of Automated Reasoning, 4, pp. 353–380, 1988. · Zbl 0662.68104 · doi:10.1007/BF00297245
[41] Stickel, M. E., ”A Prolog Technology Theorem Prover: a New Exposition and Implementation in Prolog,”Technical Note, 464, SRI International, June 1989. · Zbl 0771.68096
[42] Van Hentenryck, P., ”A Framework for Consistency Techniques in Logic Programming,”IJCAI-87, Milan, Italy.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.