?
Towards a Data Complexity Classification of Ontology-Mediated Queries with Covering
P. 1–13.
Gerasimova O., Kikot S., Zakharyaschev M.
In press
We prove a number of new syntactic and semantic sufficient and necessary conditions for ontology-mediated queries (OMQs) with one covering axiom to be in the classes AC0 and NL for data complexity, and to be L-, NL- or P-hard. We also give two new examples of very simple CONP-complete OMQs.
In book
Aachen: CEUR Workshop Proceedings, 2018.
Кузнецов А. В., Fedyanin D., Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии 2025 № 3 С. 101–109
Разработана модель для агентов, посещающих общую точку (или точки) интереса. Агенты делятся на тех, удовлетворение от посещения которых уменьшается при наличии других посетителей, и тех, удовлетворение которых растет в этом случае. Для агентов первого типа увеличение числа агентов выше определенного препятствует посещению этой точки агентами. Агенты имеют переменные параметры своего желания посещать точку и терпеть ...
Added: December 3, 2025
Zakharyaschev M., Ryzhikov V., Wałęga P., Springer Publishing Company, 2020.
Added: November 8, 2021
Zakharyaschev M., Kontchakov R., Ryzhikov V. et al., The International Joint Conference on Artificial Intelligence (IJCAI), 2020.
Traditionally, description logic has focused on represent- ing and reasoning about classes rather than relations (roles), which has been justified by the deterioration of the computa- tional properties if expressive role inclusions are added. The situation is even worse in the temporalised setting, where monodicity is viewed as an almost necessary condition for decidability. We ...
Added: November 6, 2021
Gerasimova O., Kikot S., Kurucz A. et al., , in: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning.: The International Joint Conference on Artificial Intelligence (IJCAI), 2020. P. 403–413.
Added: October 9, 2020
Obiedkov S., Sertkaya B., Zolotukhin D., , in: 32nd International Workshop on Description Logics, DL 2019; Oslo; Norway; 18 June 2019 through 21 June 2019.: CEUR-WS.org, 2019. P. 1–10.
We propose an approach for approximately completing a TBox w.r.t. a fixed model. By asking implication questions to a domain expert, our method approximates the subsumption relationships that hold in expert’s model and enriches the TBox with the newly discovered relationships between a given set of concept names. Our approach is based on Angluin’s exact ...
Added: October 29, 2019
Zakharyaschev M. et al., International Journal of Applied Mathematics and Computer Science 2019 Vol. 29 No. 1 P. 17–30
Predictive analysis gradually gains importance in industry. For instance, service engineers at Siemens diagnostic centres unveil hidden knowledge in huge amounts of historical sensor data and use it to improve the predictive systems analysing live data. Currently, the analysis is usually done using data-dependent rules that are specific to individual sensors and equipment. This dependence ...
Added: June 6, 2019
Gerasimova O., Kikot S., Podolskii V. V. et al., , in: Proceedings of the 8th international Conference on Knowledge Engineering and Semantic Web.: Berlin: Springer, 2017. P. 143–158.
This paper reports on our ongoing work that aims at a classification of conjunctive queries q according to the data complexity of answering ontology-mediated queries (A -> T v F, q). We give examples of queries from the complexity classes C in {AC0, L, NL, P, coNP}, and obtain a few syntactical conditions for C-membership ...
Added: December 3, 2017
Podolskii V. V., Zakharyaschev M., Bienvenu M. et al., , in: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems* F127745.: ACM, 2017. P. 201–216.
Our concern is the overhead of answering OWL 2QL ontology-mediated queries (OMQs) in ontology-based data access compared to evaluating their underlying tree-shaped and, more generally, bounded treewidth conjunctive queries (CQs). We show that OMQs with bounded depth ontologies have nonrecursive datalog (NDL) rewritings that can be constructed and evaluated in LOGCFL for combined complexity, and ...
Added: September 17, 2017
Gerasimova O., Podolskii V. V., Kikot S. et al., , in: Proceedings of the 30th International Workshop on Description Logics, Montpellier, France, July 18-21, 2017.: Aachen: CEUR Workshop Proceedings, 2017. Ch. 19 P. 1–12.
Thispaperreportsonourongoingworkthataimsataclassificationof conjunctive queries q according to the data complexity of answering ontology- mediated queries ({A ⊑ T ⊔ F }, q). We give examples of queries from the complexity classes C ∈ {AC0, L, NL, P, CONP}, and obtain a few syntactical conditions for C-membership and C-hardness. ...
Added: July 27, 2017
Aachen: CEUR Workshop Proceedings, 2017.
The International Workshop on Description Logics is the main annual event of the Description Logic research community. It is the forum at which those interested in description logics, from both academia and industry, meet to discuss ideas, share information, and compare experiences. The workshop explicitly welcomes submissions from researchers that are new to the area ...
Added: July 27, 2017
CEUR Workshop Proceedings, 2015.
Added: October 19, 2016
Berlin, Heidelberg: Springer, 2009.
This book constitutes the refereed proceedings of the 17th International Conference on Conceptual Structures, ICCS 2009, which took place in Moscow, Russia, on July 26-31, 2009.
The 18 papers presented together with 5 invited contributions were carefully reviewed and selected from approximately 50 submissions. Originally centered around research on knowledge representation and reasoning with conceptual graphs, ...
Added: December 9, 2012