?
Query Inseparability for Description Logic Knowledge Bases
Ch. 25. P. 25.1–25.10.
Botoeva E., Kontchakov R., Ryzhikov V., Wolter F., Zakharyaschev M.
We investigate conjunctive query inseparability of description logic (DL) knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We study the data and combined complexity of deciding KB query inseparability for fragments of Horn-ALCHI, including the DLs underpinning OWL 2 QL and OWL 2 EL. While all of these DLs are P-complete for data complexity, the combined complexity ranges from P to EXPTIME and 2EXPTIME. We also resolve two major open problems for OWL 2 QL by showing that TBox query inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both EXPTIME-complete for combined complexity.
In book
Palo Alto: AAAI Press, 2014.
Gerasimova O., Kikot S., Podolskii V. V. et al., 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 ...
Added: May 30, 2022
Zakharyaschev M., Savateev Y., Ryzhikov V., Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2021.
Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) given in linear temporal logic LTL over (Z, <) and deciding whether it is rewritable to an FO(<)-query, possibly with extra predicates. First, we observe that, in line with the circuit complexity and FO-definability of regular languages, OMQ answering ...
Added: November 6, 2021
Kravchenko T., Shevgunov T., Petrakov A., , in: Advances in Intelligent Systems and ComputingТ. 1226: Proceedings of the 9th Computer Science On-line Conference 2020. Кн. 3: Applied Informatics and Cybernetics in Intelligent Systems.: Springer, 2020. Ch. 51 P. 552–561.
Analytical justification of decision options using decision support
systems (DSS) significantly improves the quality of decisions. The use of the
currently existing DSS, which usually includes one or two decision-making
methods, does not always lead to the desired results, since each method is based
on certain assumptions and is not universal. The noticeable effect is achieved
when many decision-making methods ...
Added: August 25, 2020
Yampolsky S., Наукоемкие технологии в космических исследованиях Земли 2019 Т. 11 № 5 С. 57–64
This article addresses the particularities of military management bodies functioning automation and problems which prevent the application of an intelligent system, and the article also contains the structure of an intelligent system and offers the scheme of its application for informational and analytical maintenance for the activities of military management bodies.The possible application of an ...
Added: January 12, 2020
CEUR-WS.org, 2019.
Added: October 29, 2019
Gerasimova O., Kikot S., Zakharyaschev M., , 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 ...
Added: July 29, 2019
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 ...
Added: July 29, 2019
Ivanova I., Strand Ø., Leydesdorff L., Foresight and STI Governance 2019 Vol. 13 No. 1 P. 48–61
The innovation capacity of a system can be measured as the synergy in interactions among its parts. Synergy can be considered as a consequence of negative entropies among three parts of the system. We analyze the development of synergy value in the Norwegian innovation system in terms of mutual information among geographical, sectorial, and size ...
Added: March 4, 2019
Iskanderov Y., Яковлева А. В., Научный журнал НИУ ИТМО. Серия: Экономика и экологический менеджмент 2015 № 3 С. 210–214
The provision of quality examination of innovative projects is a complex problem because this process is associated with a significant number of parameters and characteristics of different nature, requires a high level of training of relevant professionals. One of the most relevant means of solving the problem is to award the proposed information system to ...
Added: February 7, 2019
Leydesdorff L., Ivanova I., Meyer M., , in: Springer Handbook of Science and Technology Indicators.: Springer, 2019. Ch. 16 P. 421–443.
The Triple Helix of university-industry-government relations can first be considered as an institutional network. However, the correlations in the patterns of relations provide another topology: that of a vector space. Meanings are provided from positions in this latter topology and from the perspective of hindsight. Meanings can be shared, and sharing generates redundancy. Increasing redundancy ...
Added: October 8, 2018
Tatarnikov A., Коцыняк А. М., , in: Proceedings of the 8th Spring/Summer Young Researchers’ Colloquium on Software Engineering (SYRCoSE 2014).: M.: -, 2014.
Nowadays a lot of various test generation tools are developed and applied to create tests for both software applications and hardware designs. Taking into account the size and complexity of modern projects, there is an urgent need for "smart" tools that would help maximize test coverage and keep the required effort and time to a ...
Added: December 20, 2017
S.D. Kuznetsov, D.Yu. Turdakov, Астраханцев Н. А. et al., Programming and Computer Software 2014 Vol. 40 No. 5 P. 288–295
A framework for fast text analysis, which is developed as a part of the Texterra project, is described. Texterra provides a scalable solution for the fast text processing on the basis of novel methods that exploit knowledge extracted from the Web and text documents. For the developed tools, details of the project, use cases, and ...
Added: November 26, 2017
Денис Турдаков, Астраханцев Н. А., Недумов Я. Р. et al., Труды Института системного программирования РАН 2014 Т. 26 С. 421–438
he paper presents a framework for fast text analytics developed during the Texterra project. Texterra is a technology for multilingual text mining based on novel text processing methods that exploit knowledge extracted from user-generated content. It delivers a fast scalable solution for text mining without the expensive customization. Depending on use-cases Texterra could be utilized ...
Added: November 6, 2017
Zakharyaschev M., Kontchakov R., , in: Artificial Intelligence* 234.: [б.и.], 2016. P. 78–119.
We consider conjunctive query inseparability of description logic knowledge bases with respect to a given signature - a fundamental problem in knowledge base versioning, module extraction, forgetting and knowledge exchange. We give a uniform game-theoretic characterisation of knowledge base conjunctive query inseparability and develop worst-case optimal decision algorithms for fragments of Horn-ALCHI, including the description ...
Added: September 18, 2017
Mosurovic M., Krdzavac N., Graves H. et al., Journal of Artificial Intelligence Research 2013 Vol. 47 P. 809–851
We design a decidable extension of the description logic SROIQ underlying the Web Ontology Language OWL 2. The new logic, called SR+OIQ, supports a controlled use of role axioms whose right-hand side may contain role chains or role unions. We give a tableau algorithm for checking concept satisfiability with respect to SR+OIQ ontologies and prove ...
Added: March 25, 2015
Artale A., Kontchakov R., Ryzhikov V. et al., ACM Transactions on Computational Logic 2014 Vol. 15 No. 3 P. 25.1–25.50
We design temporal description logics (TDLs) suitable for reasoning about temporal conceptual data models and investigate their computational complexity. Our formalisms are based on DL-Lite logics with three types of concept inclusions (ranging from atomic concept inclusions and disjointness to the full Booleans), as well as cardinality constraints and role inclusions. The logics are interpreted ...
Added: March 25, 2015
Artale A., Kontchakov R., Wolter F. et al., , in: Proceedings of the 23rd International Joint Conference on Artificial Intelligence.: Beijing: AAAI Press, 2013. Ch. 112 P. 711–718.
Our aim is to investigate ontology-based data access over temporal data with validity time and ontologies capable of temporal conceptual modelling. To this end, we design a temporal description logic, TQL, that extends the standard ontology language OWL 2 QL, provides basic means for temporal conceptual modelling and ensures first-order rewritability of conjunctive queries for ...
Added: March 24, 2015
Bienvenu M., Kikot S., Podolskii V. V., , in: CEUR Workshop ProceedingsVol. 1193: Informal Proceedings of the 27th International Workshop on Description Logics. Vienna, Austria, July 17-20, 2014.: Wien: CEUR Workshop Proceedings, 2014. P. 45–57.
This paper further investigates the succinctness landscape of query rewriting in OWL 2 QL. We clarify the worst-case size of positive existential (PE), non-recursive Datalog (NDL), and first-order (FO) rewritings for various classes of tree-like conjunctive queries, ranging from linear queries up to bounded treewidth queries. More specifically, we establish a superpolynomial lower bound on ...
Added: October 20, 2014