• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
August 21, 2026
Social Integration: At the Crossroads of Knowledge and Values
The International Laboratory for Social Integration Research (ILSIR) at HSE University studies the challenges faced by vulnerable groups and explores ways to help them participate fully in everyday life. To develop effective solutions, the laboratory’s researchers combine cutting-edge methods with practical fieldwork. In this interview with the HSE News Service, Laboratory Head Elena Iarskaia-Smirnova discusses the laboratory’s work.
August 18, 2026
HSE Scholar Presents Research on Postcards in Brazil and South Korea
Timur Khusyainov, Deputy Dean of theFaculty of Humanities atHSE University–Nizhny Novgorod, took part in two international conferences—the XVI World Congress of Rural Sociology in Porto Alegre, Brazil, and the 36th Annual Conference of the Alliance of Digital Humanities Organisations (DH2026) in Daejeon, South Korea. On his way to the conferences, the researcher also visited several other places, where he presented the experience of the Pochtovoe educational project.
August 18, 2026
Physicists Discover What Happens Inside a Stable Vortex
Large vortices with characteristic spiral arms are often observed in the atmosphere and the ocean. Physicists from HSE University have explained how these structures form and why they retain their shape. The researchers found that velocities at points located along the same vortex arc remain correlated even over long distances. At the same time, this correlation weakens rapidly with increasing distance from the vortex centre. These differences help explain the formation of spiral arms and may improve models of atmospheric and oceanic currents. The findings have been published in Physical Review Fluids.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

A Data Complexity and Rewritability Tetrachotomy of Ontology-Mediated Queries with a Covering Axiom

P. 403–413.
Gerasimova O., Kikot S., Kurucz A., Podolskii V. V., Zakharyaschev M.
Language: English
Full text
DOI
Text on another site
Keywords: Ontology-based data accessDescription logicsComputational aspects of knowledge representation
Publication based on the results of:
Intelligent Data Analysis in Interactive Systems for Transdisciplinary Applications (2020)

In book

Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning
The International Joint Conference on Artificial Intelligence (IJCAI), 2020.
Similar publications
Разрешение споров при помощи абстрактных аргументационных структур и его автоматизация на примере научного рецензирования
Lisanyuk E., Прокудин Д. Е., Баймуратов И. Р., Вестник Санкт-Петербургского университета. Философия и конфликтология 2026 Т. 42 № 1 С. 118–130
The process of reviewing scientific publications is hampered by the constant increase in the volume of submissions and the bias of reviewers. Artificial intelligence can speed up the scientific review process, but it is also capable of reproducing the biases embedded in the training data. We propose a formal method for representing and analyzing arguments, ...
Added: June 21, 2026
Reasoning Web. Declarative Artificial Intelligence, 16th International Summer School 2020, Oslo, Norway, June 24-26, 2020, Tutorial Lectures. Article: Temporal Ontology-Mediated Queries and First-Order Rewritability: A Short Course
Zakharyaschev M., Ryzhikov V., Wałęga P., Springer Publishing Company, 2020.
Added: November 8, 2021
Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning
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
Probably Approximately Correct Completion of Description Logic Knowledge Bases
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
Ontology–based access to temporal data with ontop: a framework proposal
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
Towards a Data Complexity Classification of Ontology-Mediated Queries with Covering
Gerasimova O., Kikot S., Zakharyaschev M., , in: Proceedings of the 31th International Workshop on Description Logics, Tempe, Arizona, October 27-29, 2018.: Aachen: CEUR Workshop Proceedings, 2018. P. 1–13.
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. ...
Added: October 22, 2018
More on the Data Complexity of Answering Ontology-Mediated Queries with a Covering Axiom
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
The complexity of ontology-based data access with OWL2QL and bounded treewidth queries
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
On the Data Complexity of Ontology-Mediated Queries with a Covering Axiom
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
Proceedings of the 30th International Workshop on Description Logics, Montpellier, France, July 18-21, 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
Description Logics Workshop, Proceedings of the 28th International Workshop on Description Logics, Athens, Greece, June 7th to 10th, 2015.
CEUR Workshop Proceedings, 2015.
Added: October 19, 2016
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit