Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.25549 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910173420847104 |
|---|---|
| author | Gogacz, Tomasz Murlak, Filip Przybyłko, Marcin Rogova, Alexandra Skrzypczak, Michał |
| author_facet | Gogacz, Tomasz Murlak, Filip Przybyłko, Marcin Rogova, Alexandra Skrzypczak, Michał |
| contents | Aiming to harmonise finite and infinite model reasoning, we initiate the study of partially finite models, where the reasoning task comes with a formula that specifies a part of the model that must be finite. We focus on the problem of partially finite query entailment in description logics (DLs): given a knowledge base (KB), a query, and a distinguished concept, decide whether the query holds in all models of the KB that interpret the distinguished concept as a finite set. To break the ground, we work with the DL S, an extension of the basic DL ALC with transitive roles, which is one of the simplest cases where finite and infinite query entailment diverge. Generalising previous results on the finite and infinite cases, we show that also partially finite entailment of conjunctive queries is in 2-exptime for S. The solution involves sophisticated infinite model surgery and goes far beyond combining the arguments for the two special cases. As a direct application, we show how the problem of query containment in the presence of closed predicates can be solved by reduction to partially finite query entailment. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_25549 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Partially Finite Model Reasoning in Description Logics Extended Version Gogacz, Tomasz Murlak, Filip Przybyłko, Marcin Rogova, Alexandra Skrzypczak, Michał Logic in Computer Science Aiming to harmonise finite and infinite model reasoning, we initiate the study of partially finite models, where the reasoning task comes with a formula that specifies a part of the model that must be finite. We focus on the problem of partially finite query entailment in description logics (DLs): given a knowledge base (KB), a query, and a distinguished concept, decide whether the query holds in all models of the KB that interpret the distinguished concept as a finite set. To break the ground, we work with the DL S, an extension of the basic DL ALC with transitive roles, which is one of the simplest cases where finite and infinite query entailment diverge. Generalising previous results on the finite and infinite cases, we show that also partially finite entailment of conjunctive queries is in 2-exptime for S. The solution involves sophisticated infinite model surgery and goes far beyond combining the arguments for the two special cases. As a direct application, we show how the problem of query containment in the presence of closed predicates can be solved by reduction to partially finite query entailment. |
| title | Partially Finite Model Reasoning in Description Logics Extended Version |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2604.25549 |