More Web Proxy on the site http://driver.im/

article

Reasoning about minimal belief and negation as failure

Author:

Riccardo RosatiAuthors Info & Claims

Journal of Artificial Intelligence Research, Volume 11, Issue 1

Pages 277 - 300

Published: 01 July 1999 Publication History

Abstract

We investigate the problem of reasoning in the propositional fragment of MBNF, the logic of minimal belief and negation as failure introduced by Lifschitz, which can be considered as a unifying framework for several nonmonotonic formalisms, including default logic, autoepistemic logic, circumscription, epistemic queries, and logic programming. We characterize the complexity and provide algorithms for reasoning in propositional MBNF. In particular, we show that skeptical entailment in propositional MBNF is Π₃^p-complete, hence it is harder than reasoning in all the above mentioned propositional formalisms for nonmonotonic reasoning. We also prove the exact correspondence between negation as failure in MBNF and negative introspection in Moore's autoepistemic logic.

References

[1]

Beringer, A., & Schaub, T. (1993). Minimal belief and negation as failure: a feasible approach. In Proc. of the 11th Nat. Conf. on Artificial Intelligence (AAAI'93), pp. 400-405.

[2]

Bochman, A. (1995). On bimodal nonmonotonic modal logics and their unimodal and nonmodal equivalents. In Proc. of the 14th Int. Joint Conf. on Artificial Intelligence (IJCAI'95), pp. 1518-1524.

[3]

Chen, J. (1994). The logic of only knowing as a unified framework for nonmonotonic reasoning. Fundamenta Informaticae, 21, 205-220.

Digital Library

[4]

Donini, F. M., Nardi, D., & Rosati, R. (1997a). Autoepistemic description logics. In Proc. of the 15th Int. Joint Conf. on Artificial Intelligence (IJCAI'97), pp. 136-141.

[5]

Donini, F. M., Nardi, D., & Rosati, R. (1997b). Ground nonmonotonic modal logics. J. of Logic and Computation, 7(4), 523-548.

[6]

Eiter, T., & Gottlob, G. (1992). Reasoning with parsimonious and moderately grounded expansions. Fundamenta Informaticae, 17(1,2), 31-54.

[7]

Eiter, T., & Gottlob, G. (1993). Propositional circumscription and extended closed world reasoning are Π₂^p-complete. Theoretical Computer Science, 114, 231-245.

Digital Library

[8]

Eiter, T., & Gottlob, G. (1995). On the computational cost of disjunctive logic programming: propositional case. Annals of Mathematics and Artificial Intelligence, 15(3,4).

[9]

Gelfond, M., & Lifschitz, V. (1988). The stable model semantics for logic programming. In Proceedings of the Fifth Logic Programming Symposium, pp. 1070-1080. The MIT Press.

[10]

Gelfond, M., & Lifschitz, V. (1990). Logic programs with classical negation. In Proceedings of the Seventh International Conference on Logic Programming, pp. 579-597. The MIT Press.

[11]

Gelfond, M., & Lifschitz, V. (1991). Classical negation in logic programs and disjunctive databases. New Generation Computing, 9, 365-385.

Digital Library

[12]

Gottlob, G. (1992). Complexity results for nonmonotonic logics. J. of Logic and Computation, 2, 397-425.

[13]

Gottlob, G. (1995). NP trees and Carnap's modal logic. J. of the ACM, 42(2), 421-457.

Digital Library

[14]

Halpern, J. Y., & Moses, Y. (1985). Towards a theory of knowledge and ignorance: Preliminary report. In Apt, K. (Ed.), Logic and models of concurrent systems. Springer-Verlag.

[15]

Halpern, J. Y., & Moses, Y. (1992). A guide to completeness and complexity for modal logics of knowledge and belief. Artificial Intelligence, 54, 319-379.

Digital Library

[16]

Inoue, K., & Sakama, C. (1994). On positive occurrences of negation as failure. In Proc. of the 4th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR'94), pp. 293-304. Morgan Kaufmann, Los Altos.

[17]

Janhunen, T. (1998). On the intertranslatability of autoepistemic, default and priority logics. In Proc. of the 6th European Workshop on Logics in Artificial Intelligence (JELIA'98), pp. 216-232.

[18]

Johnson, D. S. (1990). A catalog of complexity classes. In van Leuven, J. (Ed.), Handbook of Theoretical Computer Science, Vol. A, chap. 2. Elsevier Science Publishers (North-Holland), Amsterdam.

[19]

Kaminski, M. (1991). Embedding a default system into nonmonotonic logics. Fundamenta Informaticae, 14, 345-354.

Digital Library

[20]

Levesque, H. J. (1990). All I know: a study in autoepistemic logic. Artificial Intelligence, 42, 263-310.

Digital Library

[21]

Lifschitz, V., & Woo, T. (1992). Answer sets in general nonmonotonic reasoning (preliminary report). In Proc. of the 3rd Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR'92), pp. 603-614. Morgan Kaufmann, Los Altos.

[22]

Lifschitz, V. (1991). Nonmonotonic databases and epistemic queries. In Proc. of the 12th Int. Joint Conf. on Artificial Intelligence (IJCAI'91), pp. 381-386.

[23]

Lifschitz, V. (1994). Minimal belief and negation as failure. Artificial Intelligence, 70, 53-72.

Digital Library

[24]

Lin, F., & Shoham, Y. (1992). Epistemic semantics for fixed-point non-monotonic logics. Artificial Intelligence, 57, 271-289.

Digital Library

[25]

Marek, W., & Truszczynski, M. (1993). Nonmonotonic Logics - Context-Dependent Reasoning. Springer-Verlag.

[26]

Marek, W., Truszczynski, M., & Rajasekar, A. (1995). Complexity of computing with extended propositional logic programs. Annals of Mathematics and Artificial intelligence, 15(3,4).

[27]

Moore, R. C. (1985). Semantical considerations on nonmonotonic logic. Artificial Intelligence, 25, 75-94.

Digital Library

[28]

Niemelä, I. (1992). On the decidability and complexity of autoepistemic reasoning. Fundamenta Informaticae, 17(1,2), 117-156.

[29]

Papadimitriou, C. H. (1994). Computational Complexity. Addison Wesley Publ. Co., Reading, Massachussetts.

[30]

Reiter, R. (1990). What should a database know?. J. of Logic Programming, 14, 127-153.

Digital Library

[31]

Rosati, R. (1997). Reasoning with minimal belief and negation as failure: Algorithms and complexity. In Proc. of the 14th Nat. Conf. on Artificial Intelligence (AAAI'97), pp. 430-435. AAAI Press/The MIT Press.

[32]

Rosati, R. (1999). Reasoning about minimal knowledge in nonmonotonic modal logics. J. of Logic, Language and Information, 8(2), 187-203.

[33]

Schwarz, G. (1991). Autoepistemic logic of knowledge. In Proc. of the 1st Int. Workshop on Logic Programming and Non-monotonic Reasoning (LPNMR'91), pp. 260-274. The MIT Press.

[34]

Schwarz, G. (1992). Minimal model semantics for nonmonotonic modal logics. In Proc. of the 7th IEEE Sym. on Logic in Computer Science (LICS'92), pp. 34-43. IEEE Computer Society Press.

[35]

Schwarz, G. (1996). On embedding default logic into Moore's autoepistemic logic. Artificial Intelligence, 80, 388-392.

Digital Library

[36]

Schwarz, G., & Lifschitz, V. (1993). Extended logic programs as autoepistemic theories. In Proc. of the 2nd Int. Workshop on Logic Programming and Non-monotonic Reasoning (LPNMR'93), pp. 101-114. The MIT Press.

[37]

Schwarz, G., & Truszczynski, M. (1994). Minimal knowledge problem: a new approach. Artificial Intelligence, 67, 113-141.

Digital Library

[38]

Shoham, Y. (1987). Nonmonotonic logics: Meaning and utility. In Proc. of the 10th Int. Joint Conf. on Artificial Intelligence (IJCAI'87), pp. 388-392.

[39]

Stalnaker, R. (1993). A note on non-monotonic modal logic. Artificial Intelligence, 64(2), 183-196.

Digital Library

Cited By

Motik BRosati R(2008)Reconciling description logics and rulesJournal of the ACM10.1145/1754399.175440357:5(1-62)Online publication date: 25-Jun-2008
https://dl.acm.org/doi/10.1145/1754399.1754403
Motik BRosati R(2007)A faithful integration of description logics with logic programmingProceedings of the 20th international joint conference on Artifical intelligence10.5555/1625275.1625351(477-482)Online publication date: 6-Jan-2007
https://dl.acm.org/doi/10.5555/1625275.1625351
Rosati R(2006)Multi-modal nonmonotonic logics of minimal knowledgeAnnals of Mathematics and Artificial Intelligence10.1007/s10472-007-9046-548:3-4(169-185)Online publication date: 1-Dec-2006
https://dl.acm.org/doi/10.1007/s10472-007-9046-5
Show More Cited By

Reasoning about minimal belief and negation as failure
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
2. Theory of computation

Recommendations

Reasoning with minimal belief and negation as failure: algorithms and complexity
AAAI'97/IAAI'97: Proceedings of the fourteenth national conference on artificial intelligence and ninth conference on Innovative applications of artificial intelligence

We study the computational properties of the propositional fragment of MBNF, the logic of minimal belief and negation as failure introduced by Lifschitz, which can be considered as a unifying framework for several nonmonotonic formalisms, including ...
Minimal belief and negation as failure: a feasible approach
AAAI'93: Proceedings of the eleventh national conference on Artificial intelligence

Lifschitz introduced a logic of minimal belief and negation as failure, called MBNF, in order to provide a theory of epistemic queries to non monotonic databases. We present a feasible subsystem of MBNF which can be translated into a logic built on ...
‘Classical’ Negation in Nonmonotonic Reasoning and Logic Programming

Gelfond and Lifschitz were the first to point out the need for a symmetric negation in logic programming and they also proposed a specific semantics for such negation for logic programs with the stable semantics, which they called ‘classical’. Subsequently,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Artificial Intelligence Research

Journal of Artificial Intelligence Research Volume 11, Issue 1

July 1999

432 pages

ISSN:1076-9757

Issue’s Table of Contents

Publisher

AI Access Foundation

El Segundo, CA, United States

Publication History

Published: 01 July 1999

Published in JAIR Volume 11, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Motik BRosati R(2008)Reconciling description logics and rulesJournal of the ACM10.1145/1754399.175440357:5(1-62)Online publication date: 25-Jun-2008
https://dl.acm.org/doi/10.1145/1754399.1754403
Motik BRosati R(2007)A faithful integration of description logics with logic programmingProceedings of the 20th international joint conference on Artifical intelligence10.5555/1625275.1625351(477-482)Online publication date: 6-Jan-2007
https://dl.acm.org/doi/10.5555/1625275.1625351
Rosati R(2006)Multi-modal nonmonotonic logics of minimal knowledgeAnnals of Mathematics and Artificial Intelligence10.1007/s10472-007-9046-548:3-4(169-185)Online publication date: 1-Dec-2006
https://dl.acm.org/doi/10.1007/s10472-007-9046-5
Lakemeyer GLevesque H(2005)Only-knowingProceedings of the 20th national conference on Artificial intelligence - Volume 210.5555/1619410.1619434(633-638)Online publication date: 9-Jul-2005
https://dl.acm.org/doi/10.5555/1619410.1619434
Calvanese DDe Giacomo GLembo DLenzerini MRosati R(2005)Inconsistency tolerance in P2P data integrationProceedings of the 10th international conference on Database Programming Languages10.1007/11601524_6(90-105)Online publication date: 28-Aug-2005
https://dl.acm.org/doi/10.1007/11601524_6
Donini FNardi DRosati R(2002)Description logics of minimal knowledge and negation as failureACM Transactions on Computational Logic10.1145/505372.5053733:2(177-225)Online publication date: 1-Apr-2002
https://dl.acm.org/doi/10.1145/505372.505373

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents