9 citations · 52 across the 16 of their papers we have counts for
16 papers
Spatial Intelligence of a Self-driving Car and Rule-Based Decision Making
Stanislav Kikot
In this paper we show how rule-based decision making can be combined with traditional motion planning techniques to achieve human-like behavior of a self-driving vehicle in complex…
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…
A tetrachotomy of ontology-mediated queries with a covering axiom
Olga Gerasimova, Stanislav Kikot, Agi Kurucz +2
Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description logic ontologies and constructing their optimal rewritings to…
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…
Kripke Completeness of Strictly Positive Modal Logics over Meet-semilattices with Operators
Stanislav Kikot, Agi Kurucz, Yoshihito Tanaka +2
Our concern is the completeness problem for spi-logics, that is, sets of implications between strictly positive formulas built from propositional variables, conjunction and modal d…
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…
The decision problem of modal product logics with a diagonal, and faulty counter machines
Christopher Hampson, Stanislav Kikot, Agi Kurucz
In the propositional modal (and algebraic) treatment of two-variable first-order logic equality is modelled by a `diagonal' constant, interpreted in square products of universal fr…
A dichotomy for some elementarily generated modal logics
Stanislav Kikot
In this paper we consider the normal modal logics of elementary classes defined by first-order formulas of the form …
Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results
Meghyn Bienvenu, Stanislav Kikot, Vladimir Podolskii
This paper investigates the impact of query topology on the difficulty of answering conjunctive queries in the presence of OWL 2 QL ontologies. Our first contribution is to clarify…
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…
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…
An extension of Kracht's theorem to generalized Sahlqvist formulas
Stanislav Kikot
Sahlqvist formulas are a syntactically specified class of modal formulas proposed by Hendrik Sahlqvist in 1975. They are important because of their first-order definability and can…