• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • Национальный исследовательский университет «Высшая школа экономики»
  • Публикации ВШЭ
  • Статьи
  • A tetrachotomy of ontology-mediated queries with a covering axiom
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Приоритетные направления
  • бизнес-информатика
  • государственное и муниципальное управление
  • гуманитарные науки
  • инженерные науки
  • компьютерно-математическое
  • математика
  • менеджмент
  • право
  • социология
  • экономика
по году
  • 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
  • еще
Тематика
Новости
18 ноября 2026 г.
Три четверти различий в функциональной грамотности обусловлены генами
Исследователи НИУ ВШЭ впервые оценили на российских данных, насколько функциональная грамотность зависит от наследственности. Анализ результатов 114 пар близнецов из общероссийской выборки восьмиклассников показал: генетические различия объясняют 76% разброса в общем уровне функциональной грамотности. Результаты опубликованы в журнале Behavior Genetics.
18 ноября 2026 г.
«Наука дает мне возможность видеть красоту»
Мария Губина учится в магистратуре факультета математики НИУ ВШЭ и занимается теорией узлов. В интервью проекту «Молодые ученые Вышки» она рассказала о «числе Эрдёша», математических закономерностях вокруг нас и о том, почему ученым стоит научиться печь тортики.
17 ноября 2026 г.
Ученые НИУ ВШЭ разработали метод для обнаружения неисправностей систем охлаждения ЦОД
Исследователи НИУ ВШЭ и Уральского федерального университета разработали метод на основе искусственного интеллекта, который выявляет постепенные утечки хладагента и загрязнение теплообменников в системах охлаждения центров обработки данных. Новая модель учитывает физические связи между элементами холодильного контура, что позволяет выявлять неисправности на ранних стадиях. Результаты опубликованы в журнале IEEE Transactions on Industry Applications.

 

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

Публикации
  • Книги
  • Статьи
  • Главы в книгах
  • Препринты
  • Верификация публикаций
  • Расширенный поиск
  • Правила использования материалов
  • Наука в ВШЭ

?

A tetrachotomy of ontology-mediated queries with a covering axiom

Artificial Intelligence. 2022. Vol. 309. Article 103738.
Герасимова О. А., Kikot S., Подольский В. В., Kurucz A., Захарьящев М. В.

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 standard database queries. Originated in ontology-based data access and datalog optimisation, this problem is known to be computationally very complex in general, with no explicit syntactic characterisations available. In this article, aiming to understand the fundamental roots of this difficulty, we strip the problem to the bare bones and focus on Boolean conjunctive queries mediated by a simple covering axiom stating that one class is covered by the union of two other classes. We show that, on the one hand, these rudimentary ontology-mediated queries, called disjunctive sirups (or d-sirups), capture many features and difficulties of the general case. For example, answering d-sirups is Π2p-complete for combined complexity and can be in Image 1 or L-, NL-, P-, or coNP-complete for data complexity (with the problem of recognising FO-rewritability of d-sirups being 2ExpTime-hard); some d-sirups only have exponential-size resolution proofs, some only double-exponential-size positive existential FO-rewritings and single-exponential-size nonrecursive datalog rewritings. On the other hand, we prove a few partial sufficient and necessary conditions of FO- and (symmetric/linear-) datalog rewritability of d-sirups. Our main technical result is a complete and transparent syntactic Image 1/NL/P/coNP tetrachotomy of d-sirups with disjoint covering classes and a path-shaped Boolean conjunctive query. To obtain this tetrachotomy, we develop new techniques for establishing P- and coNP-hardness of answering non-Horn ontology-mediated queries as well as showing that they can be answered in NL.

Научное направление: Компьютерные науки
Язык: английский
Полный текст
DOI
Ключевые слова: description logicdatalogOntology-mediated queryData complexity
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Математические методы в теории сложности вычислений, теории информации и исследованиях формальных языков (2022)
Похожие публикации
Active learning of collinear magnetic Moment Tensor Potentials using the spin-MLIP package from soft-constrained spin-polarized DFT calculations: a case study of Fe-Pd
Burov A., Котыхов А. С., Aksyonov D. и др., Computer Physics Communications 2027 Vol. 330 Article 110458
Явный учет магнитных степеней свободы в межатомных потенциалах, построенных с помощью методов машинного обучения (магнитных MLIP), играет ключевую роль в корректном описании магнитных материалов и их свойств. Важным компонентом для обучения таких потенциалов являются спин-поляризованные расчеты в рамках теории функционала плотности (DFT), проводимые для состояний с неравновесными магнитными моментами — то есть расчеты DFT с ...
Добавлено: 17 ноября 2026 г.
Toward reliable false discovery rate control in classification problems under distribution shift
Кертес-Фаркаш А., Боревский А. О., Plos One 2026 Vol. 21 No. 11 P. 1–20
Background Domain shifts or batch effects can significantly degrade the performance of machine learning-based classifiers in software production without any warning. This can particularly be problematic in medical applications which involve human lives. The shift changes the shape of the prediction score distribution of the test samples compared to that of the training samples; hence, decision ...
Добавлено: 17 ноября 2026 г.
Траектории ставок как сигнал сговора: LSTM-классификация аукционов государственных закупок
Ефимов К. Д., Журнал Новой экономической ассоциации 2026 № 72 С. 105–114
В работе предлагается метод автоматического выявления картель ного поведения в электронных аукционах государственных закупок на основе анализа пол ной траектории ставок. Эмпирическая база включает 508 историй торгов за 2016–2020 гг. с электронной площадки РТС-тендер; положительный класс размечен по материалам дел ФАС России, контрольная группа сформирована из сопоставимых аукционов без зафикси рованных нарушений. Каждая сессия представлена ...
Добавлено: 13 ноября 2026 г.
Model-Dependent Prompt-Component Ablation for Medical LLM Decision Support: Application to ENT Biologics Screening
Sergey N. Koltcov, Budkovaia M., Сурков А. Ю. и др., IEEE Journal of Biomedical and Health Informatics 2026 P. 1–10
Добавлено: 13 ноября 2026 г.
Impact of 5G NR-V2X Message Losses on Connected Vehicle Warning Functions
Физулин А. В., Степанянц В. Г., Американов А. А. и др., FUTURE TRANSPORTATION 2026 Vol. 6 No. 6 Article 264
Добавлено: 12 ноября 2026 г.
Structural model of decision support system for sustainable development of oil and gas companies
Stoianova A. D., Trofimets V. Y., Matrokhina K. V., International Journal of Engineering, Transactions A: Basics 2025 Vol. 38 No. 4 P. 701–709
Добавлено: 10 ноября 2026 г.
EdFitter: a hybrid course recommendation system using large language models
Sergei Koltcov, Рюмин Д. А., Alexandr Axyonov и др., PeerJ Computer Science 2026 Article 12:e4141
Добавлено: 10 ноября 2026 г.
Assessing density equilibration in confined Liquid–Liquid interfaces
Guskov T., Gerke K., Кондратюк Н. Д. и др., Molecular Simulation 2026 Vol. 52 No. 7 P. 546 – 555
Добавлено: 10 ноября 2026 г.
Influence of nuclear quantum effects on metastable states of warm dense hydrogen
Lukyanchuk V., Норман Г. Э., Кондратюк Н. Д. и др., Scientific Reports 2026 Vol. 16 No. 1 Article 16435
Добавлено: 10 ноября 2026 г.
Machine Learning and Knowledge Discovery in Databases. Research Track and Applied Data Science Track. European Conference, ECML PKDD 2026, Naples, Italy, September 7–11, 2026, Proceedings
Cham: Springer, 2027.
Добавлено: 9 ноября 2026 г.
Artificial Intelligence for Software Engineering (AI4SE): A Review of Capabilities, Evaluation, and Verification Challenges
Avdoshin S.M., Pesotskaya E.Y., Proceedings of the Institute for System Programming of the RAS 2026 Vol. 38 No. 6, part 2 P. 133–146
Добавлено: 8 ноября 2026 г.
MFL-ScrollNet: Recurrent Sliding-Window Detection for Panoramic Pipeline Magnetic Flux Leakage Images
Aleksei Samarin, Belous F., Торопов А. Г. и др., Technologies 2026 Vol. 14 No. 11 P. 1–21
Добавлено: 8 ноября 2026 г.
Proceedings 2026 IEEE International Conference on Joint Cloud Computing JCC 2026
IEEE Computer Society (Conference Publishing Services, CPS), 2026.
Добавлено: 7 ноября 2026 г.
Detecting the undetectable: benchmarking AI-generated text
Sergey Avdoshin, Elena Pesotskaya, Салех Х. М. и др., Procedia Computer Science 2026 Vol. 292 P. 1332–1341
Добавлено: 7 ноября 2026 г.
PrimeKV: Preserving critical KV cache without attention scores for long-context inference
Чжан Ч., Ильвовский Д. А., Neurocomputing 2027 Vol. 710
Добавлено: 5 ноября 2026 г.
Data complexity: An FCA-based approach
Бузмаков А. В., Дудырев Е. О., Кузнецов С. О. и др., International Journal of Approximate Reasoning 2024 Vol. 165 Article 109084
Добавлено: 24 февраля 2025 г.
Conference: 28th International Symposium on Temporal Representation and Reasoning, TIME 2021
Захарьящев М. В., Саватеев Ю. В., Ryzhikov V., Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2021.
Добавлено: 6 ноября 2021 г.
First-order rewritability of ontology-mediated queries in linear temporal logic
Artale A., Kontchakov R., Kovtunova A. и др., Artificial Intelligence 2021 Vol. 299 Article 103536
Добавлено: 30 сентября 2021 г.
32nd International Workshop on Description Logics, DL 2019; Oslo; Norway; 18 June 2019 through 21 June 2019
CEUR-WS.org, 2019.
Добавлено: 29 октября 2019 г.
Checking the Data Complexity of Ontology-Mediated Queries: A Case Study with Non-uniform CSPs and Polyanna
Герасимова О. А., Kikot S., Захарьящев М. В., , in: Description Logic, Theory Combination, and All That.: Berlin: Springer, 2019. P. 329–351.
It has recently been shown that first-order- and datalog-rewritability of ontology-mediated queries (OMQs) with expressive ontologies can be checked in NExpTime using a reduction to CSPs. In this paper, we present a case study for OMQs with Boolean conjunctive queries and a fixed ontology consisting of a single covering axiom 𝐴 -> 𝐹 v 𝑇, A -> F v T, possibly supplemented with ...
Добавлено: 29 июля 2019 г.
Description Logic, Theory Combination, and All That
Berlin: Springer, 2019.
This Festschrift has been put together on the occasion of Franz Baader's 60th birthday to celebrate his fundamental and highly influential scientific contributions. The 30 papers in this volume cover several scientific areas that Franz Baader has been working on during the last three decades, including  description logics,  term rewriting, and the combination of decision procedures.  We  hope that ...
Добавлено: 29 июля 2019 г.
Games for query inseparability of description logic knowledge bases
Захарьящев М. В., Kontchakov R., , in: Artificial Intelligence* 234.: [б.и.], 2016. P. 78–119.
Добавлено: 18 сентября 2017 г.
The complexity of ontology-based data access with OWL2QL and bounded treewidth queries
Подольский В. В., Захарьящев М. В., Bienvenu M. и др., , in: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems* F127745.: ACM, 2017. P. 201–216.
Добавлено: 17 сентября 2017 г.
Query Inseparability for Description Logic Knowledge Bases
Botoeva E., Kontchakov R., Ryzhikov V. и др., , in: Proceedings, Fourteenth International Conference on Principles of Knowledge Representation and Reasoning (KR-14).: Palo Alto: AAAI Press, 2014. Ch. 25 P. 25.1–25.10.
Добавлено: 25 марта 2015 г.
  • О ВЫШКЕ
  • Цифры и факты
  • Руководство и структура
  • Устойчивое развитие в НИУ ВШЭ
  • Преподаватели и сотрудники
  • Корпуса и общежития
  • Закупки
  • Обращения граждан в НИУ ВШЭ
  • Фонд целевого капитала
  • Противодействие коррупции
  • Сведения о доходах, расходах, об имуществе и обязательствах имущественного характера
  • Сведения об образовательной организации
  • Людям с ограниченными возможностями здоровья
  • Единая платежная страница
  • Работа в Вышке
  • ОБРАЗОВАНИЕ
  • Лицей
  • Довузовская подготовка
  • Олимпиады
  • Прием в бакалавриат
  • Вышка+
  • Прием в магистратуру
  • Аспирантура
  • Дополнительное образование
  • Центр развития карьеры
  • Бизнес-инкубатор ВШЭ
  • Образовательные партнерства
  • Обратная связь и взаимодействие с получателями услуг
  • НАУКА
  • Научные подразделения
  • Исследовательские проекты
  • Мониторинги
  • Диссертационные советы
  • Защиты диссертаций
  • Академическое развитие
  • Конкурсы и гранты
  • Внешние научно-информационные ресурсы
  • РЕСУРСЫ
  • Библиотека
  • Издательский дом ВШЭ
  • Книжный магазин «БукВышка»
  • Типография
  • Медиацентр
  • Журналы ВШЭ
  • Публикации
  • http://www.minobrnauki.gov.ru/
    Министерство науки и высшего образования РФ
  • https://edu.gov.ru/
    Министерство просвещения РФ
  • https://elearning.hse.ru/mooc
    Массовые открытые онлайн-курсы
  • НИУ ВШЭ1993–2026
  • Адреса и контакты
  • Условия использования материалов
  • Политика обработки персональных данных
  • Правила применения рекомендательных технологий в НИУ ВШЭ
  • Карта сайта
Редактору