Minimal Model Reasoning in Description Logics: Don’t Try This at Home! Article Swipe

PDF

Federica Di Stefano , Quentin Manière , Magdalena Ortiz , Mantas Šimkus ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.24963/kr.2025/27

Reasoning with minimal models has always been at the core of many knowledge representation techniques, but we still have only a limited understanding of this problem in Description Logics (DLs). Minimization of some selected predicates---letting the remaining predicates vary or be fixed, as proposed in circumscription---has been explored and exhibits high complexity. The case of `pure' minimal models, where the extension of all predicates must be minimal, has remained largely uncharted. We address this problem in popular DLs and obtain surprisingly negative results: concept satisfiability in minimal models is undecidable already for EL. This undecidability also extends to a very restricted fragment of tuple-generating dependencies. To regain decidability, we impose acyclicity conditions on the TBox that bring the worst-case complexity below double exponential time and allow us to establish a connection with the recently studied pointwise circumscription; we also derive results in data complexity. We conclude with a brief excursion to the DL-Lite family, where a positive result was known for DL-Lite_core, but our investigation establishes ExpSpace-hardness already for its extension DL-Lite_horn.

Related Topics

Role Model (Singer)

Tesla Model Y

Dominique Jackson (Model)

Smith & Wesson Model 29

Business Process Model And Notation

Kara Young (Model)

Technology Acceptance Model

Colt Model 1903 Pocket Hammerless

Boeing-Stearman Model 75

Debye Model

J. Alexander (Model)

Smith & Wesson Model 686

Concepts

No concepts available.

Metadata

Type: article
Landing Page: https://doi.org/10.24963/kr.2025/27
PDF: https://proceedings.kr.org/2025/27/kr2025-0027-di-stefano-et-al.pdf
OA Status: gold
OpenAlex ID: https://openalex.org/W4415903195

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4415903195

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.24963/kr.2025/27

Digital Object Identifier
Title: Minimal Model Reasoning in Description Logics: Don’t Try This at Home!

Work title
Type: article

OpenAlex work type
Publication year: 2025

Year of publication
Publication date: 2025-11-01

Full publication date if available
Authors: Federica Di Stefano, Quentin Manière, Magdalena Ortiz, Mantas Šimkus

List of authors in order
Landing page: https://doi.org/10.24963/kr.2025/27

Publisher landing page
PDF URL: https://proceedings.kr.org/2025/27/kr2025-0027-di-stefano-et-al.pdf

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: gold

Open access status per OpenAlex
OA URL: https://proceedings.kr.org/2025/27/kr2025-0027-di-stefano-et-al.pdf

Direct OA link when available
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W4415903195
doi	https://doi.org/10.24963/kr.2025/27
ids.doi	https://doi.org/10.24963/kr.2025/27
ids.openalex	https://openalex.org/W4415903195
fwci
type	article
title	Minimal Model Reasoning in Description Logics: Don’t Try This at Home!
biblio.issue
biblio.volume
biblio.last_page	280
biblio.first_page	271
is_xpac	False
apc_list
apc_paid
language
locations[0].id	doi:10.24963/kr.2025/27
locations[0].is_oa	True
locations[0].source
locations[0].license
locations[0].pdf_url	https://proceedings.kr.org/2025/27/kr2025-0027-di-stefano-et-al.pdf
locations[0].version	publishedVersion
locations[0].raw_type	proceedings-article
locations[0].license_id
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Proceedings of the TwentySecond International Conference on Principles of Knowledge Representation and Reasoning
locations[0].landing_page_url	https://doi.org/10.24963/kr.2025/27
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5051966978
authorships[0].author.orcid	https://orcid.org/0000-0002-6570-7598
authorships[0].author.display_name	Federica Di Stefano
authorships[0].affiliations[0].raw_affiliation_string	Institute of Logic and Compuation, TU Wien
authorships[0].author_position	first
authorships[0].raw_author_name	Federica Di Stefano
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Institute of Logic and Compuation, TU Wien
authorships[1].author.id	https://openalex.org/A5064544374
authorships[1].author.orcid	https://orcid.org/0000-0001-9618-8359
authorships[1].author.display_name	Quentin Manière
authorships[1].countries	DE
authorships[1].affiliations[0].institution_ids	https://openalex.org/I926574661
authorships[1].affiliations[0].raw_affiliation_string	Universität Leipzig
authorships[1].affiliations[1].raw_affiliation_string	ScaDS.AI
authorships[1].institutions[0].id	https://openalex.org/I926574661
authorships[1].institutions[0].ror	https://ror.org/03s7gtk40
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I926574661
authorships[1].institutions[0].country_code	DE
authorships[1].institutions[0].display_name	Leipzig University
authorships[1].author_position	middle
authorships[1].raw_author_name	Quentin Manière
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	ScaDS.AI, Universität Leipzig
authorships[2].author.id	https://openalex.org/A5082472539
authorships[2].author.orcid	https://orcid.org/0000-0002-2344-9658
authorships[2].author.display_name	Magdalena Ortiz
authorships[2].affiliations[0].raw_affiliation_string	Institute of Logic and Compuation, TU Wien
authorships[2].author_position	middle
authorships[2].raw_author_name	Magdalena Ortiz
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	Institute of Logic and Compuation, TU Wien
authorships[3].author.id	https://openalex.org/A5079813467
authorships[3].author.orcid	https://orcid.org/0000-0003-0632-0294
authorships[3].author.display_name	Mantas Šimkus
authorships[3].affiliations[0].raw_affiliation_string	Institute of Logic and Compuation, TU Wien
authorships[3].author_position	last
authorships[3].raw_author_name	Mantas Šimkus
authorships[3].is_corresponding	False
authorships[3].raw_affiliation_strings	Institute of Logic and Compuation, TU Wien
has_content.pdf	True
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://proceedings.kr.org/2025/27/kr2025-0027-di-stefano-et-al.pdf
open_access.oa_status	gold
open_access.any_repository_has_fulltext	False
created_date	2025-11-05T00:00:00
display_name	Minimal Model Reasoning in Description Logics: Don’t Try This at Home!
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic
cited_by_count	0
locations_count	1
best_oa_location.id	doi:10.24963/kr.2025/27
best_oa_location.is_oa	True
best_oa_location.source
best_oa_location.license
best_oa_location.pdf_url	https://proceedings.kr.org/2025/27/kr2025-0027-di-stefano-et-al.pdf
best_oa_location.version	publishedVersion
best_oa_location.raw_type	proceedings-article
best_oa_location.license_id
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Proceedings of the TwentySecond International Conference on Principles of Knowledge Representation and Reasoning
best_oa_location.landing_page_url	https://doi.org/10.24963/kr.2025/27
primary_location.id	doi:10.24963/kr.2025/27
primary_location.is_oa	True
primary_location.source
primary_location.license
primary_location.pdf_url	https://proceedings.kr.org/2025/27/kr2025-0027-di-stefano-et-al.pdf
primary_location.version	publishedVersion
primary_location.raw_type	proceedings-article
primary_location.license_id
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Proceedings of the TwentySecond International Conference on Principles of Knowledge Representation and Reasoning
primary_location.landing_page_url	https://doi.org/10.24963/kr.2025/27
publication_date	2025-11-01
publication_year	2025
referenced_works_count	0
abstract_inverted_index.a	20, 98, 129, 147, 155
abstract_inverted_index.To	105
abstract_inverted_index.We	71, 144
abstract_inverted_index.as	42
abstract_inverted_index.at	7
abstract_inverted_index.be	40, 65
abstract_inverted_index.in	26, 44, 75, 85, 141
abstract_inverted_index.is	88
abstract_inverted_index.of	10, 23, 31, 54, 61, 102
abstract_inverted_index.on	112
abstract_inverted_index.or	39
abstract_inverted_index.to	97, 127, 150
abstract_inverted_index.us	126
abstract_inverted_index.we	16, 108, 137
abstract_inverted_index.DLs	77
abstract_inverted_index.EL.	92
abstract_inverted_index.The	52
abstract_inverted_index.all	62
abstract_inverted_index.and	48, 78, 124
abstract_inverted_index.but	15, 162
abstract_inverted_index.for	91, 160, 168
abstract_inverted_index.has	4, 67
abstract_inverted_index.its	169
abstract_inverted_index.our	163
abstract_inverted_index.the	8, 35, 59, 113, 117, 132, 151
abstract_inverted_index.was	158
abstract_inverted_index.TBox	114
abstract_inverted_index.This	93
abstract_inverted_index.also	95, 138
abstract_inverted_index.been	6, 46
abstract_inverted_index.case	53
abstract_inverted_index.core	9
abstract_inverted_index.data	142
abstract_inverted_index.have	18
abstract_inverted_index.high	50
abstract_inverted_index.many	11
abstract_inverted_index.must	64
abstract_inverted_index.only	19
abstract_inverted_index.some	32
abstract_inverted_index.that	115
abstract_inverted_index.this	24, 73
abstract_inverted_index.time	123
abstract_inverted_index.vary	38
abstract_inverted_index.very	99
abstract_inverted_index.with	1, 131, 146
abstract_inverted_index.allow	125
abstract_inverted_index.below	120
abstract_inverted_index.brief	148
abstract_inverted_index.bring	116
abstract_inverted_index.known	159
abstract_inverted_index.still	17
abstract_inverted_index.where	58, 154
abstract_inverted_index.(DLs).	29
abstract_inverted_index.Logics	28
abstract_inverted_index.`pure'	55
abstract_inverted_index.always	5
abstract_inverted_index.derive	139
abstract_inverted_index.double	121
abstract_inverted_index.fixed,	41
abstract_inverted_index.impose	109
abstract_inverted_index.models	3, 87
abstract_inverted_index.obtain	79
abstract_inverted_index.regain	106
abstract_inverted_index.result	157
abstract_inverted_index.DL-Lite	152
abstract_inverted_index.address	72
abstract_inverted_index.already	90, 167
abstract_inverted_index.concept	83
abstract_inverted_index.extends	96
abstract_inverted_index.family,	153
abstract_inverted_index.largely	69
abstract_inverted_index.limited	21
abstract_inverted_index.minimal	2, 56, 86
abstract_inverted_index.models,	57
abstract_inverted_index.popular	76
abstract_inverted_index.problem	25, 74
abstract_inverted_index.results	140
abstract_inverted_index.studied	134
abstract_inverted_index.conclude	145
abstract_inverted_index.exhibits	49
abstract_inverted_index.explored	47
abstract_inverted_index.fragment	101
abstract_inverted_index.minimal,	66
abstract_inverted_index.negative	81
abstract_inverted_index.positive	156
abstract_inverted_index.proposed	43
abstract_inverted_index.recently	133
abstract_inverted_index.remained	68
abstract_inverted_index.results:	82
abstract_inverted_index.selected	33
abstract_inverted_index.Reasoning	0
abstract_inverted_index.establish	128
abstract_inverted_index.excursion	149
abstract_inverted_index.extension	60, 170
abstract_inverted_index.knowledge	12
abstract_inverted_index.pointwise	135
abstract_inverted_index.remaining	36
abstract_inverted_index.acyclicity	110
abstract_inverted_index.complexity	119
abstract_inverted_index.conditions	111
abstract_inverted_index.connection	130
abstract_inverted_index.predicates	37, 63
abstract_inverted_index.restricted	100
abstract_inverted_index.uncharted.	70
abstract_inverted_index.worst-case	118
abstract_inverted_index.Description	27
abstract_inverted_index.complexity.	51, 143
abstract_inverted_index.establishes	165
abstract_inverted_index.exponential	122
abstract_inverted_index.techniques,	14
abstract_inverted_index.undecidable	89
abstract_inverted_index.Minimization	30
abstract_inverted_index.surprisingly	80
abstract_inverted_index.DL-Lite_core,	161
abstract_inverted_index.DL-Lite_horn.	171
abstract_inverted_index.decidability,	107
abstract_inverted_index.dependencies.	104
abstract_inverted_index.investigation	164
abstract_inverted_index.understanding	22
abstract_inverted_index.representation	13
abstract_inverted_index.satisfiability	84
abstract_inverted_index.undecidability	94
abstract_inverted_index.circumscription;	136
abstract_inverted_index.tuple-generating	103
abstract_inverted_index.ExpSpace-hardness	166
abstract_inverted_index.predicates---letting	34
abstract_inverted_index.circumscription---has	45
cited_by_percentile_year
countries_distinct_count	1
institutions_distinct_count	4
citation_normalized_percentile