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

article

Description logics of minimal knowledge and negation as failure

Authors:

Francesco M. Donini,

Riccardo RosatiAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 3, Issue 2

Pages 177 - 225

https://doi.org/10.1145/505372.505373

Published: 01 April 2002 Publication History

Abstract

We present description logics of minimal knowledge and negation as failure (MKNF-DLs), which augment description logics with modal operators interpreted according to Lifschitz's nonmonotonic logic MKNF. We show the usefulness of MKNF-DLs for a formal characterization of a wide variety of nonmonotonic features that are both commonly available inframe-based systems, and needed in the development of practical knowledge-based applications: defaults, integrity constraints, role, and concept closure. In addition, we provide a correct and terminating calculus for query answering in a very expressive MKNF-DL.

References

[1]

BAADER, F., BURCKERT, H.-J., HOLLUNDER, B., NUTT,W.,AND SIEKMANN, J. H. 1990. Concept logics. In Computational Logics, Symposium Proceedings, J. W. Lloyd, Ed. Springer-Verlag, 177-201.]]

[2]

BAADER,F.AND HOLLUNDER, B. 1992. Embedding defaults into terminological knowledge representation formalisms. In Proceedings of the 3rd International Conference on the Principles of Knowledge Representation and Reasoning (KR'92). Morgan Kaufmann, Los Altos, 306-317.]]

Digital Library

[3]

BAADER,F.AND HOLLUNDER, B. 1995. Embedding defaults into terminological knowledge representation formalisms. J. Auto. Reason. 14, 149-180.]]

[4]

BERGAMASCHI,S.AND SARTORI, C. 1992. On taxonomic reasoning in conceptual design. ACMTrans. Data. Syst. 17, 3, 385-422.]]

Digital Library

[5]

BORGIDA, A. 1995. Description logics for data management. IEEE Trans. Knowl. Data Eng. 7,5, 671-682.]]

Digital Library

[6]

BRACHMAN, R. J. 1992. "Reducing" CLASSIC to practice: Knowledge representation meets reality. In Proceedings of the 3rd International Conference on the Principles of Knowledge Representation and Reasoning (KR'92). Morgan Kaufmann, Los Altos, 247-258.]]

[7]

BRACHMAN,R.J.AND LEVESQUE, H. J., Eds. 1985. Readings in Knowledge Representation. Morgan Kaufmann, Los Altos.]]

Digital Library

[8]

BUCHHEIT, M., DONINI,F.M.,AND SCHAERF, A. 1993. Decidable reasoning in terminological knowledge representation systems. J. Artif. Intell. Res. 1, 109-138.]]

Digital Library

[9]

CALVANESE, D., DE GIACOMO, G., LENZERINI, M., NARDI,D.,AND ROSATI, R. 1998. Description logic framework for information integration. In Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning (KR'98). 2-13.]]

[10]

CALVANESE, D., LENZERINI, M., AND NARDI, D. 1994. A unified framework for class based representation formalisms. In Proceedings of the 4th International Conference on the Principles of Knowledge Representation and Reasoning (KR'94), J. Doyle, E. Sandewall, and P. Torasso, Eds. Morgan Kaufmann, Los Altos, Bonn (Germany), 109-120.]]

[11]

DONINI, F. M., LENZERINI, M., NARDI, D., NUTT,W.,AND SCHAERF, A. 1992. Adding epistemic operators to concept languages. In Proceedings of the 3rd International Conference on the Principles of Knowledge Representation and Reasoning (KR'92). Morgan Kaufmann, Los Altos, 342-353.]]

[12]

DONINI, F. M., LENZERINI, M., NARDI,D.,AND SCHAERF, A. 1996. Reasoning in description logics. In Principles of Knowledge Representation, G. Brewka, Ed. Studies in Logic, Language and Information. CSLI Publications, 193-238.]]

Digital Library

[13]

DONINI, F. M., LENZERINI, M., NARDI,D.,AND SCHAERF, A. 1998a. AL-log: integrating datalog and description logics. J. Intell. Inform. Syst. 10, 227-252.]]

Digital Library

[14]

DONINI, F. M., LENZERINI, M., NARDI, D., SCHAERF, A., AND NUTT, W. 1998b. An epistemic operator for description logics. Artificial Intelligence 100, 1-2, 225-274.]]

Digital Library

[15]

DONINI, F. M., NARDI,D.,AND ROSATI, R. 1995. Non-first-order features in concept languages. In Proceedings of the 4th Conference of the Italian Association for Artificial Intelligence (AI*IA'95). Number 992 in Lecture Notes in Artificial Intelligence. Springer-Verlag, 91-102.]]

Digital Library

[16]

DONINI, F. M., NARDI,D.,AND ROSATI, R. 1997a. Autoepistemic description logics. In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI'97). 136-141.]]

[17]

DONINI, F. M., NARDI,D.,AND ROSATI, R. 1997b. Ground nonmonotonic modal logics. J. Logic Comput. 7, 4 (Aug.), 523-548.]]

[18]

EITER, T., GOTTLOB,G.,AND MANNILLA, H. 1997. Disjunctive Datalog. ACMTrans. Data. Syst. 22,3, 364-418.]]

Digital Library

[19]

ETHERINGTON,D.AND REITER, R. 1983. On inheritance networks with exceptions. In Proceedings of the 3th National Conference on Artificial Intelligence (AAAI'83). 104-108.]]

[20]

FIKES,R.AND KEHLER, T. 1985. The role of frame-based representation in reasoning. Commun. ACM 28, 9, 904-920.]]

Digital Library

[21]

FITTING, M. 1983. Proof Methods for Modal and Intuitionistic Logics. Reidel.]]

[22]

GOTTLOB, G. 1992. Complexity results for nonmonotonic logics. J. Logic Comput. 2, 397-425.]]

[23]

GOTTLOB, G. 1995. NP trees and Carnap's modal logic. J. ACM 42, 2, 421-457.]]

Digital Library

[24]

HAYES, P. J. 1979. The logic of frames. In Frame Conceptions and Text Understanding, D. Metzing, Ed. Walter de Gruyter and Co., 46-61. Republished in {Brachman and Levesque 1985}.]]

[25]

KAKAS,A.AND MANCARELLA, P. 1990. Generalized stable models: a semantics for abduction. In Proceedings of the 9th European Conference on Artificial Intelligence (ECAI'90). 385-391.]]

[26]

KARP, P. D. 1992. The design space of knowledge representation systems. Tech. Rep. SRI AI Technical Note 520, SRI International, Menlo Park (CA, USA).]]

[27]

KIFER, M., LAUSEN,G.,AND WU, J. 1995. Logical foundations of Object-Oriented and frame-based languages. J. ACM 42, 4, 741-843.]]

Digital Library

[28]

LAKEMEYER, G. 1996. Limited reasoning in first-order knowledge bases with full introspection. Artificial Intelligence 84, 209-255.]]

Digital Library

[29]

LEVESQUE, H. J. 1984. Foundations of a functional approach to knowledge representation. Artificial Intelligence 23, 155-212.]]

Digital Library

[30]

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

Digital Library

[31]

LEVY,A.Y.AND ROUSSET, M.-C. 1998. Verification of knowledge bases based on containment checking. Artificial Intelligence 101(1-2), 227-250.]]

Digital Library

[32]

LIFSCHITZ, V. 1991. Nonmonotonic databases and epistemic queries. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI'91). 381-386.]]

Digital Library

[33]

LIFSCHITZ, V. 1994. Minimal belief and negation as failure. Artificial Intelligence 70, 53-72.]]

Digital Library

[34]

MACGREGOR, R. 1988. A deductive pattern matcher. In Proceedings of the 7th National Conference on Artificial Intelligence (AAAI'88). 403-408.]]

[35]

MAREK,W.AND TRUSZCZYNSKI, M. 1993. Nonmonotonic Logics-Context-Dependent Reasoning. Springer-Verlag.]]

Digital Library

[36]

NADO,R.AND FIKES, R. 1987. Semantically sound inheritance for a formally defined frame language with defaults. In Proceedings of the 6th National Conference on Artificial Intelligence (AAAI'87). 443-448.]]

[37]

NEBEL, B. 1990. Reasoning and Revision in Hybrid Representation Systems. Lecture Notes in Artificial Intelligence, vol. 422. Springer-Verlag.]]

Digital Library

[38]

NIEMELA, I. 1992. On the decidability and complexity of autoepistemic reasoning. Fundamenta Informaticae 17, 1,2, 117-156.]]

Digital Library

[39]

NIEMELA, I. 1993. Autoepistemic logic as a unified basis for nonmonotonic reasoning. Ph.D. dissertation Department of Computer Science, Helsinki University of Technology, Finland.]]

[40]

PADGHAM,L.AND ZHANG, T. 1993. A terminological logic with defaults. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI'93). 662-668.]]

[41]

PATEL-SCHNEIDER, P. F., MCGUINESS, D. L., BRACHMAN, R. J., RESNICK,L.A.,AND BORGIDA, A. 1991. The CLASSIC knowledge representation system: Guiding principles and implementation rational. SIGART Bull. 2, 3, 108-113.]]

Digital Library

[42]

QUANTZ,J.AND ROYER, V. 1992. A preference semantics for defaults in terminological logics. In Proceedings of the 3rd International Conference on the Principles of Knowledge Representation and Reasoning (KR'92). Morgan Kaufmann, Los Altos, 294-305.]]

[43]

REITER, R. 1990. What should a database know? J. Logic Program. 14, 127-153.]]

Digital Library

[44]

REITER,R.AND CRISCUOLO, G. 1981. On interacting defaults. In Proceedings of the 7th International Joint Conference on Artificial Intelligence (IJCAI'81). 270-276.]]

[45]

ROSATI, R. 1998. Reducing query answering to satisfiability in nonmonotonic logics. In Proceedings of the 15th National Conference on Artificial Intelligence (AAAI'98). AAAI Press/ The MIT Press, 853-858.]]

Digital Library

[46]

ROSATI, R. 1999a. Reasoning about minimal belief and negation as failure. J. Artif. Intell. Res. 11, 277-300.]]

Digital Library

[47]

ROSATI, R. 1999b. Towards first-order nonmonotonic reasoning. In Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'99). Lecture Notes in Artificial Intelligence, vol. 1730. Springer-Verlag, 332-346.]]

Digital Library

[48]

SCHMIDT-SCHAUSS,M.AND SMOLKA, G. 1991. Attributive concept descriptions with complements. Artificial Intelligence 48, 1, 1-26.]]

Digital Library

[49]

STRACCIA, U. 1993. Default inheritance reasoning in hybrid KL-ONE-style logics. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI'93). Morgan Kaufmann, Los Altos, Chamb~ry (France), 676-681.]]

[50]

WOODS,W.A.AND SCHMOLZE, J. G. 1992. The KL-ONE family. In Semantic Networks in Artificial Intelligence, F. W. Lehmann, Ed. Pergamon Press, 133-178. Published as a special issue of Computers & Mathematics with Applications, Volume 23, Number 2-9.]]

Cited By

Alviano MGiordano LTheseider Dupré D(2024)Complexity and scalability of defeasible reasoning in many-valued weighted knowledge bases with typicalityJournal of Logic and Computation10.1093/logcom/exae03834:8(1469-1499)Online publication date: 5-Aug-2024
https://doi.org/10.1093/logcom/exae038
Lieto APozzato G(2024)Two semantic interpretations of probabilities in description logics of typicalityLogic Journal of the IGPL10.1093/jigpal/jzae086Online publication date: 22-Jul-2024
https://doi.org/10.1093/jigpal/jzae086
Lukumbuzya SOrtiz MŠimkus M(2024)Datalog rewritability and data complexity of ALCHOIQ with closed predicatesArtificial Intelligence10.1016/j.artint.2024.104099330:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.artint.2024.104099
Show More Cited By

Index Terms

Description logics of minimal knowledge and negation as failure
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Nonmonotonic, default reasoning and belief revision
2. Theory of computation
  1. Logic
    1. Modal and temporal logics

Recommendations

Complexities of Horn Description Logics

Description logics (DLs) have become a prominent paradigm for representing knowledge in a variety of application areas, partly due to their ability to achieve a favourable balance between expressivity of the logic and performance of reasoning. Horn ...
Multi-modal nonmonotonic logics of minimal knowledge

In this paper we introduce multi-modal logics of minimal knowledge. Such a family of logics constitutes the first proposal in the field of epistemic nonmonotonic logic in which the three following aspects are simultaneously addressed: (1) the ...
Disentangling FDE-Based Paraconsistent Modal Logics

The relationships between various modal logics based on Belnap and Dunn's paraconsistent four-valued logic FDE are investigated. It is shown that the paraconsistent modal logic $$\mathsf{BK}^\Box $$BKź, which lacks a primitive possibility operator $$\...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 3, Issue 2

April 2002

157 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/505372

Issue’s Table of Contents

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 2002

Published in TOCL Volume 3, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

181
Total Citations
View Citations
1,198
Total Downloads

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

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alviano MGiordano LTheseider Dupré D(2024)Complexity and scalability of defeasible reasoning in many-valued weighted knowledge bases with typicalityJournal of Logic and Computation10.1093/logcom/exae03834:8(1469-1499)Online publication date: 5-Aug-2024
https://doi.org/10.1093/logcom/exae038
Lieto APozzato G(2024)Two semantic interpretations of probabilities in description logics of typicalityLogic Journal of the IGPL10.1093/jigpal/jzae086Online publication date: 22-Jul-2024
https://doi.org/10.1093/jigpal/jzae086
Lukumbuzya SOrtiz MŠimkus M(2024)Datalog rewritability and data complexity of ALCHOIQ with closed predicatesArtificial Intelligence10.1016/j.artint.2024.104099330:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.artint.2024.104099
Bonatti PPetrova ISauro LElkind E(2023)Optimizing the computation of overriding in DLN (extended abstract)Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/771(6860-6862)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/771
Pozzato GSpinnicchia M(2023)A Defeasible Description Logic for AbductionAIxIA 2023 – Advances in Artificial Intelligence10.1007/978-3-031-47546-7_6(74-87)Online publication date: 6-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-47546-7_6
Hussain AWu WTang Z(2022)An MDE-based methodology for closed-world integrity constraint checking in the semantic webWeb Semantics: Science, Services and Agents on the World Wide Web10.1016/j.websem.2022.10071774:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.websem.2022.100717
Bonatti PPetrova ISauro L(2022)Optimizing the computation of overriding in DL N Artificial Intelligence10.1016/j.artint.2022.103764311:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.artint.2022.103764
Thapa RGiese M(2022)Mapping Relational Database Constraints to SHACLThe Semantic Web – ISWC 202210.1007/978-3-031-19433-7_13(214-230)Online publication date: 23-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-19433-7_13
Loukil FGhedira-Guegan CBoukadi KBenharkat ABenkhelifa E(2021)Data Privacy Based on IoT Device Behavior Control Using BlockchainACM Transactions on Internet Technology10.1145/343477621:1(1-20)Online publication date: 5-Jan-2021
https://dl.acm.org/doi/10.1145/3434776
de Vilhena PPottier F(2021)A separation logic for effect handlersProceedings of the ACM on Programming Languages10.1145/34343145:POPL(1-28)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434314
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents