Games for query inseparability of description logic knowledge bases

Малышев Д. С., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791–801

Добавлено: 16 февраля 2024 г.

Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering with a Covering Axiom

Герасимова О. А., Макаров И. А., Severin N., IEEE Access 2023 Vol. 11 P. 88074–88086

The problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontology constraints increases. Logic-based methods use theoretical constructions to obtain efficient rewritings ...

Добавлено: 5 января 2024 г.

The discrete Fourier transform over the binary finite field

Sergei Valentinovich Fedorenko, IEEE Access 2023 Vol. 11 P. 62771–62779

Добавлено: 19 июля 2023 г.

Complexity function and complexity of validity of modal and superintuitionistic propositional logics

Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566–1595

Добавлено: 6 января 2023 г.

Some cases of polynomial solvability of the edge coloring problem that are generated by forbidden 8-edge subcubic forests

Добавлено: 31 декабря 2022 г.

On a Countable Family of Boundary Graph Classes for the Dominating Set Problem

G. S. Dakhno, D. S. Malyshev, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 1 P. 25–31

Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Если это множество конечно, то он называется конечно определенным. Понятие граничного класса является полезным инструментом анализа вычислительной сложности задач на графах в семействе конечно определенных классов. Задача о доминирующем множестве для заданного графа состоит в ...

Добавлено: 6 декабря 2022 г.

Comparing the Computational Complexity of Monomials and Elements of Finite Abelian Groups

Кочергин В. В., Moscow University Mathematics Bulletin 2022 Vol. 77 No. 3 P. 113–119

Добавлено: 29 октября 2022 г.

A tetrachotomy of ontology-mediated queries with a covering axiom

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

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 ...

Добавлено: 30 мая 2022 г.

Complexity of finite-variable fragments of propositional temporal and modal logics of computation

Рыбаков М. Н., Shkatov D., Theoretical Computer Science 2022 Vol. 925 P. 45–60

Добавлено: 12 мая 2022 г.

An intractability result for the vertex 3-colourability problem

Malyshev D. S., Приставченко О. В., Optimization Letters 2022 Vol. 16 P. 1403–1409

Добавлено: 25 февраля 2022 г.

On computational complexity of set automata

Рубцов А. А., Вялый М. Н., Information and Computation 2021 Vol. 281 Article 104797

Добавлено: 2 февраля 2022 г.

Conference: 28th International Symposium on Temporal Representation and Reasoning, TIME 2021

Захарьящев М. В., Саватеев Ю. В., Ryzhikov V., Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2021.

Добавлено: 6 ноября 2021 г.

Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning

Захарьящев М. В., Kontchakov R., Ryzhikov V. и др., The International Joint Conference on Artificial Intelligence (IJCAI), 2020.

Добавлено: 6 ноября 2021 г.

No-Rainbow Problem and the Surjective Constraint Satisfaction Problem

Жук Д. Н., , in: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).: [б.и.], 2021. P. 1–7.

Добавлено: 8 сентября 2021 г.

Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP

Barto L., Brady Z., Bulatov M. и др., , in: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).: [б.и.], 2021. P. 1–13.

Добавлено: 8 сентября 2021 г.

On 3-colouring of graphs with short faces and bounded maximum vertex degree

Сироткин Д. В., Малышев Д. С., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760–766

Добавлено: 5 июня 2021 г.

Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes

Развенская О. О., Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2021 Vol. 15 No. 1 P. 97–117

Добавлено: 23 апреля 2021 г.

Efficient Algorithm for Finding Roots of Error-Locator Polynomials

Sergei Valentinovich Fedorenko, IEEE Access 2021 Vol. 9 P. 38673–38686

Добавлено: 15 апреля 2021 г.

Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem

Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706–721

Добавлено: 30 января 2021 г.

The vertex colourability problem for {claw,butterfly}-free graphs is polynomial-time solvable

Малышев Д. С., Optimization Letters 2021 Vol. 15 No. 2 P. 311–326

Добавлено: 6 января 2021 г.

Low-rank matrix approximation in the infinity norm

Gillis N., Шитов Я. Н., Linear Algebra and its Applications 2019 Vol. 581 P. 367–382

Добавлено: 11 ноября 2020 г.

Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions

Грибанов Д. В., Малышев Д. С., Мокеев Д. Б., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 P. 480–489

Добавлено: 30 октября 2020 г.

A Proof of CSP Dichotomy Conjecture

Жук Д. Н., , in: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS).: IEEE, 2017. P. 331–342.

Добавлено: 29 октября 2020 г.