2 citations · 3 across the 2 of their papers we have counts for
6 papers
Deciding boundedness of monadic sirups
Stanislav Kikot, Agi Kurucz, Vladimir Podolskii +1
We show that deciding boundedness (aka FO-rewritability) of monadic single rule datalog programs (sirups) is 2Exp-hard, which matches the upper bound known since 1988 and finally s…
Completeness of logics with the transitive closure modality and related logics
Stanislav Kikot, Ilya Shapirovsky, Evgeny Zolin
We give a sufficient condition for Kripke completeness of modal logics enriched with the transitive closure modality. More precisely, we show that if a logic admits what we call de…
On monotonic determinacy and rewritability for recursive queries and views
Michael Benedikt, Stanislav Kikot, Piotr Ostropolski-Nalewaja +1
A query Q is monotonically determined over a set of views if Q can be expressed as a monotonic function of the view image. In the case of relational algebra views and queries, mono…
Non-finitely axiomatisable modal product logics with infinite canonical axiomatisations
Christopher Hampson, Stanislav Kikot, Agi Kurucz +1
Our concern is the axiomatisation problem for modal and algebraic logics that correspond to various fragments of two-variable first-order logic with counting quantifiers. In partic…
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…