2018/08/09 by Tomasz Gogacz, Gogacz, Tomasz, Yazmín Ibáñez-García +3 · 2 citations
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Semantic Web and Ontologies #Service-Oriented Architecture and Web Services
paper · pdf · doi:10.48550/arxiv.1808.03130
openalex publication_date 2018/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of finite ontology mediated query answering (FOMQA), the\nvariant of OMQA where the represented world is assumed to be finite, and thus\nonly finite models of the ontology are considered. We adopt the most typical\nsetting with unions of conjunctive queries and ontologies expressed in\ndescription logics (DLs). The study of FOMQA is relevant in settings that are\nnot finitely controllable. This is the case not only for DLs without the finite\nmodel property, but also for those allowing transitive role declarations. When\ntransitive roles are allowed, evaluating queries is challenging: FOMQA is\nundecidable for SHOIF and only known to be decidable for the Horn fragment of\nALCIF. We show decidability of FOMQA for three proper fragments of SOIF: SOI,\nSOF, and SIF. Our approach is to characterise models relevant for deciding\nfinite query entailment. Relying on a certain regularity of these models, we\ndevelop automata-based decision procedures with optimal complexity bounds.\n