257 citations · 435 across the 18 of their papers we have counts for
18 papers
Fusions of One-Variable First-Order Modal Logics
Roman Kontchakov, Dmitry Shkatov, Frank Wolter
We investigate preservation results for the independent fusion of one-variable first-order modal logics. We show that, without equality, Kripke completeness and decidability of glo…
Decidability in First-Order Modal Logic with Non-Rigid Constants and Definite Descriptions
Alessandro Artale, Christopher Hampson, Roman Kontchakov +2
While modal extensions of decidable fragments of first-order logic are usually undecidable, their monodic counterparts, in which formulas in the scope of modal operators have at mo…
Non-Rigid Designators in Modal and Temporal Free Description Logics (Extended Version)
Alessandro Artale, Roman Kontchakov, Andrea Mazzullo +1
Definite descriptions, such as 'the General Chair of KR 2024', are a semantically transparent device for object identification in knowledge representation. In first-order modal log…
First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries
Alessandro Artale, Roman Kontchakov, Alisa Kovtunova +3
Aiming at ontology-based data access to temporal data, we design two-dimensional temporal ontology and query languages by combining logics from the (extended) DL-Lite family with l…
First-Order Rewritability of Ontology-Mediated Queries in Linear Temporal Logic
Alessandro Artale, Roman Kontchakov, Alisa Kovtunova +3
We investigate ontology-based data access to temporal data. We consider temporal ontologies given in linear temporal logic LTL interpreted over discrete time (Z,<). Queries are giv…
Efficient Handling of SPARQL OPTIONAL for OBDA (Extended Version)
Guohui Xiao, Roman Kontchakov, Benjamin Cogrel +2
OPTIONAL is a key feature in SPARQL for dealing with missing information. While this operator is used extensively, it is also known for its complexity, which can make efficient eva…
The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov +3
Our concern is the overhead of answering OWL 2 QL ontology-mediated queries (OMQs) in ontology-based data access compared to evaluating their underlying tree-shaped and bounded tre…
Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov +2
We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL 2 QL: the succinctness problem for first-order…
Theoretically Optimal Datalog Rewritings for OWL 2 QL Ontology-Mediated Queries
Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov +2
We show that, for OWL 2 QL ontology-mediated queries with (i) ontologies of bounded depth and conjunctive queries of bounded treewidth, (ii) ontologies of bounded depth and bounded…
On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Shallow Chases
Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii +1
We investigate the size of first-order rewritings of conjunctive queries over OWL 2 QL ontologies of depth 1 and 2 by means of hypergraph programs computing Boolean functions. Both…
The DL-Lite Family and Relations
Alessandro Artale, Diego Calvanese, Roman Kontchakov +1
The recently introduced series of description logics under the common moniker DL-Lite has attracted attention of the description logic and semantic web communities due to the low c…
The Complexity of Clausal Fragments of LTL
A. Artale, R. Kontchakov, V. Ryzhikov +1
We introduce and investigate a number of fragments of propo- sitional temporal logic LTL over the flow of time (Z, <). The fragments are defined in terms of the available temporal…
A Cookbook for Temporal Conceptual Data Modelling with Description Logics
Alessandro Artale, Roman Kontchakov, Vladislav Ryzhikov +1
We design temporal description logics suitable for reasoning about temporal conceptual data models and investigate their computational complexity. Our formalisms are based on DL-Li…
Exponential Lower Bounds and Separation for Query Rewriting
Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii +1
We establish connections between the size of circuits and formulas computing monotone Boolean functions and the size of first-order and nonrecursive Datalog rewritings for conjunct…
Topological Logics with Connectedness over Euclidean Spaces
Roman Kontchakov, Yavor Nenov, Ian Pratt-Hartmann +1
We consider the quantifier-free languages, Bc and Bc0, obtained by augmenting the signature of Boolean algebras with a unary predicate representing, respectively, the property of b…
Combining Spatial and Temporal Logics: Expressiveness vs. Complexity
D. Gabelaia, R. Kontchakov, A. Kurucz +2
In this paper, we construct and investigate a hierarchy of spatio-temporal formalisms that result from various combinations of propositional spatial and temporal logics such as the…
On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces
Roman Kontchakov, Yavor Nenov, Ian Pratt-Hartmann +1
We investigate (quantifier-free) spatial constraint languages with equality, contact and connectedness predicates as well as Boolean operations on regions, interpreted over low-dim…
Spatial logics with connectedness predicates
Roman Kontchakov, Ian Pratt-Hartmann, Frank Wolter +1
We consider quantifier-free spatial logics, designed for qualitative spatial representation and reasoning in AI, and extend them with the means to represent topological connectedne…