{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:19:06Z","timestamp":1762273146393,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031435126"},{"type":"electronic","value":"9783031435133"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T00:00:00Z","timestamp":1694649600000},"content-version":"vor","delay-in-days":256,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>\nWe define LE-<jats:inline-formula><jats:tex-math>$$\\mathcal {ALC}$$<\/jats:tex-math><\/jats:inline-formula>, a generalization of the description logic <jats:inline-formula><jats:tex-math>$$\\mathcal {ALC}$$<\/jats:tex-math><\/jats:inline-formula> based on the propositional logic of general (i.e.\u00a0not necessarily distributive) lattices, and semantically interpreted on relational structures based on formal contexts from Formal Concept Analysis (FCA). The description logic LE-<jats:inline-formula><jats:tex-math>$$\\mathcal {ALC}$$<\/jats:tex-math><\/jats:inline-formula> 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-<jats:inline-formula><jats:tex-math>$$\\mathcal {ALC}$$<\/jats:tex-math><\/jats:inline-formula>, provide a tableaux algorithm for checking the consistency of LE-<jats:inline-formula><jats:tex-math>$$\\mathcal {ALC}$$<\/jats:tex-math><\/jats:inline-formula> knowledge bases with acyclic TBoxes, and show its termination, soundness and completeness. Interestingly, consistency checking for LE-<jats:inline-formula><jats:tex-math>$$\\mathcal {ALC}$$<\/jats:tex-math><\/jats:inline-formula> with acyclic TBoxes is in <jats:sc>PTIME<\/jats:sc>, while the complexity of the consistency checking of classical <jats:inline-formula><jats:tex-math>$$\\mathcal {ALC}$$<\/jats:tex-math><\/jats:inline-formula> with acyclic TBoxes is <jats:sc>PSPACE<\/jats:sc>-complete.<\/jats:p>","DOI":"10.1007\/978-3-031-43513-3_4","type":"book-chapter","created":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T14:02:36Z","timestamp":1694613756000},"page":"49-69","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Non-distributive Description Logic"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2220-1383","authenticated-orcid":false,"given":"Ineke","family":"van der Berg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8973-7011","authenticated-orcid":false,"given":"Andrea","family":"De Domenico","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4845-3821","authenticated-orcid":false,"given":"Giuseppe","family":"Greco","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3664-7757","authenticated-orcid":false,"given":"Krishna B.","family":"Manoorkar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9656-7527","authenticated-orcid":false,"given":"Alessandra","family":"Palmigiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9218-5449","authenticated-orcid":false,"given":"Mattia","family":"Panettiere","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,14]]},"reference":[{"issue":"5","key":"4_CR1","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1109\/TSMC.2013.2280440","volume":"44","author":"J Atif","year":"2014","unstructured":"Atif, J., Hudelot, C., Bloch, I.: Explanatory reasoning for image understanding using formal concept analysis and description logics. IEEE Trans. Syst. Man Cybern. Syst. 44(5), 552\u2013570 (2014)","journal-title":"IEEE Trans. Syst. Man Cybern. Syst."},{"key":"4_CR2","volume-title":"The Description Logic Handbook: Theory, Implementation and Applications","author":"F Baader","year":"2003","unstructured":"Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.: The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, Cambridge (2003)"},{"key":"4_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/9781139025355","volume-title":"An Introduction to Description Logic","author":"F Baader","year":"2017","unstructured":"Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic. Cambridge University Press, Cambridge (2017)"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-540-24651-0_24","volume-title":"Concept Lattices","author":"F Baader","year":"2004","unstructured":"Baader, F., Sertkaya, B.: Applying formal concept analysis to description logics. In: Eklund, P. (ed.) ICFCA 2004. LNCS (LNAI), vol. 2961, pp. 261\u2013286. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24651-0_24"},{"key":"4_CR5","doi-asserted-by":"publisher","unstructured":"van der Berg, I., De Domenico, A., Greco, G., Manoorkar, K.B., Palmigiano, A., Panettiere, M.: Labelled calculi for the logics of rough concepts. In: Banerjee, M., Sreejith, A.V. (eds.) Logic and Its Applications, ICLA 2023. LNCS, vol. 13963, pp. 172\u2013188. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-26689-8_13","DOI":"10.1007\/978-3-031-26689-8_13"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-319-67582-4_3","volume-title":"Scalable Uncertainty Management","author":"S Borgwardt","year":"2017","unstructured":"Borgwardt, S., Pe\u00f1aloza, R.: Fuzzy description logics \u2013 a survey. In: Moral, S., Pivert, O., S\u00e1nchez, D., Mar\u00edn, N. (eds.) SUM 2017. LNCS (LNAI), vol. 10564, pp. 31\u201345. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-67582-4_3"},{"key":"4_CR7","unstructured":"Conradie, W., et al.: Modal reduction principles across relational semantics. arXiv preprint arXiv:2202.00899 (2022)"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/j.ins.2020.05.074","volume":"561","author":"W Conradie","year":"2021","unstructured":"Conradie, W., et al.: Rough concepts. Inf. Sci. 561, 371\u2013413 (2021)","journal-title":"Inf. Sci."},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Conradie, W., Frittella, S., Palmigiano, A., Piazzai, M., Tzimoulis, A., Wijnberg, N.M.: Toward an epistemic-logical theory of categorization. In: Electronic Proceedings in Theoretical Computer Science, EPTCS 251 (2017)","DOI":"10.4204\/EPTCS.251.12"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-662-52921-8_10","volume-title":"Logic, Language, Information, and Computation","author":"W Conradie","year":"2016","unstructured":"Conradie, W., Frittella, S., Palmigiano, A., Piazzai, M., Tzimoulis, A., Wijnberg, N.M.: Categories: how i learned to stop worrying and love two sorts. In: V\u00e4\u00e4n\u00e4nen, J., Hirvonen, \u00c5., de Queiroz, R. (eds.) WoLLIC 2016. LNCS, vol. 9803, pp. 145\u2013164. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-52921-8_10"},{"issue":"9","key":"4_CR11","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1016\/j.apal.2019.04.003","volume":"170","author":"W Conradie","year":"2019","unstructured":"Conradie, W., Palmigiano, A.: Algorithmic correspondence and canonicity for non-distributive logics. Ann. Pure Appl. Logic 170(9), 923\u2013974 (2019)","journal-title":"Ann. Pure Appl. Logic"},{"key":"4_CR12","unstructured":"Conradie, W., Palmigiano, A., Robinson, C., Wijnberg, N.: Non-distributive logics: from semantics to meaning. In: Rezus, A. (ed.) Contemporary Logic and Computing, Landscapes in Logic, vol. 1, pp. 38\u201386. College Publications (2020)"},{"key":"4_CR13","doi-asserted-by":"publisher","unstructured":"Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-59830-2","DOI":"10.1007\/978-3-642-59830-2"},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2015.05.001","volume":"226","author":"L Giordano","year":"2015","unstructured":"Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Semantic characterization of rational closure: from propositional logic to description logics. Artif. Intell. 226, 1\u201333 (2015)","journal-title":"Artif. Intell."},{"issue":"2","key":"4_CR15","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1093\/logcom\/exab082","volume":"32","author":"L Giordano","year":"2022","unstructured":"Giordano, L., Gliozzi, V., Theseider Dupr\u00e9, D.: A conditional, a fuzzy and a probabilistic interpretation of self-organizing maps. J. Log. Comput. 32(2), 178\u2013205 (2022)","journal-title":"J. Log. Comput."},{"issue":"7","key":"4_CR16","first-page":"1367","volume":"28","author":"G Greco","year":"2016","unstructured":"Greco, G., Ma, M., Palmigiano, A., Tzimoulis, A., Zhao, Z.: Unified correspondence as a proof-theoretic tool. J. Log. Comput. 28(7), 1367\u20131442 (2016)","journal-title":"J. Log. Comput."},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"104967","DOI":"10.1016\/j.knosys.2019.104967","volume":"186","author":"Y Jiang","year":"2019","unstructured":"Jiang, Y.: Semantifying formal concept analysis using description logics. Knowl. Based Syst. 186, 104967 (2019)","journal-title":"Knowl. Based Syst."},{"issue":"5","key":"4_CR18","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1080\/0952813X.2019.1672799","volume":"32","author":"A Lieto","year":"2020","unstructured":"Lieto, A., Pozzato, G.L.: A description logic framework for commonsense conceptual combination integrating typicality, probabilities and cognitive heuristics. J. Exp. Theoret. Artif. Intell. 32(5), 769\u2013804 (2020)","journal-title":"J. Exp. Theoret. Artif. Intell."},{"issue":"1","key":"4_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0269888912000306","volume":"28","author":"ZM Ma","year":"2013","unstructured":"Ma, Z.M., Zhang, F., Wang, H., Yan, L.: An overview of fuzzy description logics for the semantic web. Knowl. Eng. Rev. 28(1), 1\u201334 (2013)","journal-title":"Knowl. Eng. Rev."},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.entcs.2011.06.010","volume":"273","author":"V de Paiva","year":"2011","unstructured":"de Paiva, V., Haeusler, E.H., Rademaker, A.: Constructive description logics hybrid-style. Electron. Notes Theoret. Comput. Sci. 273, 21\u201331 (2011)","journal-title":"Electron. Notes Theoret. Comput. Sci."},{"key":"4_CR21","unstructured":"Shilov, N.V., Han, S.Y.: A proposal of description logic on concept lattices. In: Proceedings of the Fifth International Conference on Concept Lattices and their Applications, pp. 165\u2013176 (2007)"},{"issue":"2","key":"4_CR22","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s10849-017-9249-z","volume":"26","author":"C Wurm","year":"2017","unstructured":"Wurm, C.: Language-theoretic and finite relation models for the (full) Lambek calculus. J. Logic Lang. Inform. 26(2), 179\u2013214 (2017). https:\/\/doi.org\/10.1007\/s10849-017-9249-z","journal-title":"J. Logic Lang. Inform."}],"container-title":["Lecture Notes in Computer Science","Automated Reasoning with Analytic Tableaux and Related Methods"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43513-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T14:03:14Z","timestamp":1694613794000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43513-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031435126","9783031435133"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43513-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"14 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TABLEAUX","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Automated Reasoning with Analytic Tableaux and Related Methods","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tableaux2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/tableaux2023.tableaux-ar.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3 (2.92)","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}