Non-distributive Description Logic

Ineke van der Berg; Andrea De Domenico; Giuseppe Greco; Krishna B. Manoorkar; Alessandra Palmigiano; Mattia Panettiere

doi:10.1007/978-3-031-43513-3_4

Non-distributive Description Logic

Ineke van der Berg, Andrea De Domenico^*, Giuseppe Greco, Krishna B. Manoorkar, Alessandra Palmigiano, Mattia Panettiere

^*Corresponding author for this work

Ethics, Governance and Society

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We define LE- $$\mathcal {ALC}$$, a generalization of the description logic $$\mathcal {ALC}$$ based on the propositional logic of general (i.e. not necessarily distributive) lattices, and semantically interpreted on relational structures based on formal contexts from Formal Concept Analysis (FCA). The description logic LE- $$\mathcal {ALC}$$ allows us to formally describe databases with objects, features, and formal concepts, represented according to FCA as Galois-stable sets of objects and features. We describe ABoxes and TBoxes in LE- $$\mathcal {ALC}$$, provide a tableaux algorithm for checking the consistency of LE- $$\mathcal {ALC}$$ knowledge bases with acyclic TBoxes, and show its termination, soundness and completeness. Interestingly, consistency checking for LE- $$\mathcal {ALC}$$ with acyclic TBoxes is in PTIME, while the complexity of the consistency checking of classical $$\mathcal {ALC}$$ with acyclic TBoxes is PSPACE-complete.

Original language	English
Title of host publication	Automated Reasoning with Analytic Tableaux and Related Methods - 32nd International Conference, TABLEAUX 2023, Proceedings
Editors	Revantha Ramanayake, Josef Urban
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	49-69
Number of pages	21
ISBN (Print)	9783031435126
DOIs	https://doi.org/10.1007/978-3-031-43513-3_4
Publication status	Published - 2023
Event	32nd International Conference on Automated Reasoning with Analytic Tableaux and Related Methods, TABLEAUX 2023 - Prague, Czech Republic Duration: 18 Sept 2023 → 21 Sept 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14278 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	32nd International Conference on Automated Reasoning with Analytic Tableaux and Related Methods, TABLEAUX 2023
Country/Territory	Czech Republic
City	Prague
Period	18/09/23 → 21/09/23

Bibliographical note

Funding Information:
This paper is partially funded by the EU MSCA (grant No. 101007627). The first author is funded by the National Research Foundation of South Africa (grant No. 140841). The third and fourth authors are partially funded by the NWO grant KIVI.2019.001.

Publisher Copyright:
© 2023, The Author(s).

Funding

This paper is partially funded by the EU MSCA (grant No. 101007627). The first author is funded by the National Research Foundation of South Africa (grant No. 140841). The third and fourth authors are partially funded by the NWO grant KIVI.2019.001.

Keywords

Description logic
Formal Concept Analysis
LE-logics
Tableaux algorithm

Access to Document

10.1007/978-3-031-43513-3_4

Persistent URL (handle)

Persistent link

Cite this

van der Berg, I., De Domenico, A., Greco, G., Manoorkar, K. B., Palmigiano, A., & Panettiere, M. (2023). Non-distributive Description Logic. In R. Ramanayake, & J. Urban (Eds.), Automated Reasoning with Analytic Tableaux and Related Methods - 32nd International Conference, TABLEAUX 2023, Proceedings (pp. 49-69). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14278 LNAI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-43513-3_4

van der Berg, Ineke ; De Domenico, Andrea ; Greco, Giuseppe et al. / Non-distributive Description Logic. Automated Reasoning with Analytic Tableaux and Related Methods - 32nd International Conference, TABLEAUX 2023, Proceedings. editor / Revantha Ramanayake ; Josef Urban. Springer Science and Business Media Deutschland GmbH, 2023. pp. 49-69 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c402eb7f679c49c49254c6076e1f6b48,

title = "Non-distributive Description Logic",

abstract = "We define LE- $$\mathcal {ALC}$$, a generalization of the description logic $$\mathcal {ALC}$$ based on the propositional logic of general (i.e. not necessarily distributive) lattices, and semantically interpreted on relational structures based on formal contexts from Formal Concept Analysis (FCA). The description logic LE- $$\mathcal {ALC}$$ allows us to formally describe databases with objects, features, and formal concepts, represented according to FCA as Galois-stable sets of objects and features. We describe ABoxes and TBoxes in LE- $$\mathcal {ALC}$$, provide a tableaux algorithm for checking the consistency of LE- $$\mathcal {ALC}$$ knowledge bases with acyclic TBoxes, and show its termination, soundness and completeness. Interestingly, consistency checking for LE- $$\mathcal {ALC}$$ with acyclic TBoxes is in PTIME, while the complexity of the consistency checking of classical $$\mathcal {ALC}$$ with acyclic TBoxes is PSPACE-complete.",

keywords = "Description logic, Formal Concept Analysis, LE-logics, Tableaux algorithm",

author = "{van der Berg}, Ineke and {De Domenico}, Andrea and Giuseppe Greco and Manoorkar, {Krishna B.} and Alessandra Palmigiano and Mattia Panettiere",

note = "Funding Information: This paper is partially funded by the EU MSCA (grant No. 101007627). The first author is funded by the National Research Foundation of South Africa (grant No. 140841). The third and fourth authors are partially funded by the NWO grant KIVI.2019.001. Publisher Copyright: {\textcopyright} 2023, The Author(s).; 32nd International Conference on Automated Reasoning with Analytic Tableaux and Related Methods, TABLEAUX 2023 ; Conference date: 18-09-2023 Through 21-09-2023",

year = "2023",

doi = "10.1007/978-3-031-43513-3_4",

language = "English",

isbn = "9783031435126",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "49--69",

editor = "Revantha Ramanayake and Josef Urban",

booktitle = "Automated Reasoning with Analytic Tableaux and Related Methods - 32nd International Conference, TABLEAUX 2023, Proceedings",

address = "Germany",

}

van der Berg, I , De Domenico, A , Greco, G , Manoorkar, KB , Palmigiano, A & Panettiere, M 2023, Non-distributive Description Logic. in R Ramanayake & J Urban (eds), Automated Reasoning with Analytic Tableaux and Related Methods - 32nd International Conference, TABLEAUX 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14278 LNAI, Springer Science and Business Media Deutschland GmbH, pp. 49-69, 32nd International Conference on Automated Reasoning with Analytic Tableaux and Related Methods, TABLEAUX 2023, Prague, Czech Republic, 18/09/23. https://doi.org/10.1007/978-3-031-43513-3_4

Non-distributive Description Logic. / van der Berg, Ineke ; De Domenico, Andrea ; Greco, Giuseppe et al.
Automated Reasoning with Analytic Tableaux and Related Methods - 32nd International Conference, TABLEAUX 2023, Proceedings. ed. / Revantha Ramanayake; Josef Urban. Springer Science and Business Media Deutschland GmbH, 2023. p. 49-69 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14278 LNAI).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Non-distributive Description Logic

AU - van der Berg, Ineke

AU - De Domenico, Andrea

AU - Greco, Giuseppe

AU - Manoorkar, Krishna B.

AU - Palmigiano, Alessandra

AU - Panettiere, Mattia

N1 - Funding Information: This paper is partially funded by the EU MSCA (grant No. 101007627). The first author is funded by the National Research Foundation of South Africa (grant No. 140841). The third and fourth authors are partially funded by the NWO grant KIVI.2019.001. Publisher Copyright: © 2023, The Author(s).

PY - 2023

Y1 - 2023

N2 - We define LE- $$\mathcal {ALC}$$, a generalization of the description logic $$\mathcal {ALC}$$ based on the propositional logic of general (i.e. not necessarily distributive) lattices, and semantically interpreted on relational structures based on formal contexts from Formal Concept Analysis (FCA). The description logic LE- $$\mathcal {ALC}$$ allows us to formally describe databases with objects, features, and formal concepts, represented according to FCA as Galois-stable sets of objects and features. We describe ABoxes and TBoxes in LE- $$\mathcal {ALC}$$, provide a tableaux algorithm for checking the consistency of LE- $$\mathcal {ALC}$$ knowledge bases with acyclic TBoxes, and show its termination, soundness and completeness. Interestingly, consistency checking for LE- $$\mathcal {ALC}$$ with acyclic TBoxes is in PTIME, while the complexity of the consistency checking of classical $$\mathcal {ALC}$$ with acyclic TBoxes is PSPACE-complete.

AB - We define LE- $$\mathcal {ALC}$$, a generalization of the description logic $$\mathcal {ALC}$$ based on the propositional logic of general (i.e. not necessarily distributive) lattices, and semantically interpreted on relational structures based on formal contexts from Formal Concept Analysis (FCA). The description logic LE- $$\mathcal {ALC}$$ allows us to formally describe databases with objects, features, and formal concepts, represented according to FCA as Galois-stable sets of objects and features. We describe ABoxes and TBoxes in LE- $$\mathcal {ALC}$$, provide a tableaux algorithm for checking the consistency of LE- $$\mathcal {ALC}$$ knowledge bases with acyclic TBoxes, and show its termination, soundness and completeness. Interestingly, consistency checking for LE- $$\mathcal {ALC}$$ with acyclic TBoxes is in PTIME, while the complexity of the consistency checking of classical $$\mathcal {ALC}$$ with acyclic TBoxes is PSPACE-complete.

KW - Description logic

KW - Formal Concept Analysis

KW - LE-logics

KW - Tableaux algorithm

UR - http://www.scopus.com/inward/record.url?scp=85172418706&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85172418706&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-43513-3_4

DO - 10.1007/978-3-031-43513-3_4

M3 - Conference contribution

AN - SCOPUS:85172418706

SN - 9783031435126

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 49

EP - 69

BT - Automated Reasoning with Analytic Tableaux and Related Methods - 32nd International Conference, TABLEAUX 2023, Proceedings

A2 - Ramanayake, Revantha

A2 - Urban, Josef

PB - Springer Science and Business Media Deutschland GmbH

T2 - 32nd International Conference on Automated Reasoning with Analytic Tableaux and Related Methods, TABLEAUX 2023

Y2 - 18 September 2023 through 21 September 2023

ER -

van der Berg I , De Domenico A , Greco G , Manoorkar KB , Palmigiano A , Panettiere M. Non-distributive Description Logic. In Ramanayake R, Urban J, editors, Automated Reasoning with Analytic Tableaux and Related Methods - 32nd International Conference, TABLEAUX 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 49-69. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-43513-3_4

Non-distributive Description Logic

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this