?
Theoretically optimal datalog rewritings for OWL 2 QL ontology-mediated queries
P. 1–13.
Bienvenu M., Kikot S., Kontchakov R., Podolskii V. V., Zakharyaschev M.
We show that, for OWL 2 QL ontology-mediated queries with (i) ontologies of bounded depth and conjunctive queries of bounded treewidth, (ii) ontologies of bounded depth and bounded-leaf tree-shaped conjunctive queries, and (iii) arbitrary ontologies and bounded-leaf tree-shaped conjunctive queries, one can construct and evaluate nonrecursive datalog rewritings by, respectively, LOGCFL, NL and LOGCFL algorithms, which matches the optimal combined complexity. © 2016, CEUR-WS. All rights reserved.
Language:
English
Alexander Rubtsov, Chudinov N., , in: 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024).: Leibniz International Proceedings in Informatics (LIPIcs), 2024. Ch. 80 P. 80:1–80:13.
We present a computational model for Parsing Expression Grammars (PEGs). The predecessor of PEGs top-down parsing languages (TDPLs) were discovered by A. Birman and J. Ullman in the 1960-s, B. Ford showed in 2004 that both formalisms recognize the same class named Parsing Expression Languages (PELs). A. Birman and J. Ullman established such important properties ...
Added: November 24, 2024
Rubtsov A. A., Vyalyi M., , in: Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, ProceedingsVol. 10846.: Springer, 2018. P. 295–307.
We consider a computational model which is known as set automata.
The set automata are one-way finite automata with an additional storage—the set. There are two kinds of set automata—the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by Kutrib et al. in 2014 in [2, 3].
In this ...
Added: June 21, 2018
Улан-Удэ: Издательство Бурятского госуниверситета, 2017.
The collection represents proceedings of the 5th school-seminar "Syntax and Semantics of Logic Systems" (Ulan-Ude, 08.08.2017 - 12.08.2017). The conference subject area includes: theory of models and universal algebra; theory of boolean and finite-valued functions; formal languages and logic calculus; mathematical logic in education. ...
Added: September 22, 2017
Botoeva E., Zakharyaschev M., Kontchakov R. et al., , in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015.: Palo Alto: AAAI Press, 2015. P. 4240–4246.
Deciding inseparability of description logic knowledge bases (KBs) with respect to conjunctive queries is fundamental for many KB engineering and maintenance tasks including versioning, module extraction, knowledge exchange and forgetting. We study the combined and data complexity of this inseparability problem for fragments of Horn-ALCHI, including the description logics underpinning OWL 2 QL and OWL ...
Added: September 18, 2017
Zakharyaschev M., Artale A., Kontchakov R. et al., , in: Proceedings of the National Conference on Artificial Intelligence.: American Association for Artificial Intelligence (AAAI) Press, 2015. P. 1417–1423.
We design a tractable Horn fragment of the Halpern-Shoham temporal logic and extend it to interval-based temporal description logics, instance checking in which is P-complete for both combined and data complexity. ...
Added: September 18, 2017
American Association for Artificial Intelligence (AAAI) Press, 2015.
Added: September 18, 2017
Konev B. Y., Lutz C., Wolter F. et al., , in: 25th International Joint Conference on Artificial Intelligence.: [б.и.], 2016. P. 1153–1159.
We investigate the problem of conservative rewritability of a TBox T in a description logic (DL) L into a TBox T' in a weaker DL L'. We focus on model-conservative rewritability (T' entails T and all models of T are expandable to models of T'), subsumption-conservative rewritability (T' entails T and all subsumptions in the ...
Added: September 18, 2017
[б.и.], 2016.
Added: September 18, 2017
Zakharyaschev M., Botoeva E., Konev B. Y. et al., , in: 12th International Summer School on Reasoning Web Summer School, RW 2016Issue 9885.: [б.и.], 2017. P. 27–89.
The question whether an ontology can safely be replaced by another, possibly simpler, one is fundamental for many ontology engineering and maintenance tasks. It underpins, for example, ontology versioning, ontology modularization, forgetting, and knowledge exchange. What ‘safe replacement’ means depends on the intended application of the ontology. If, for example, it is used to query ...
Added: September 18, 2017
Bienvenu M., Kikot S., Kontchakov R. et al., , in: Proceedings of the 30th International Workshop on Description Logics, Montpellier, France, July 18-21, 2017.: Aachen: CEUR Workshop Proceedings, 2017. P. 1–12.
Our concern is answering ontology-mediated queries (Ο q), whereΟ is a set of linear tgds and q a conjunctive query (CQ) of bounded hypertree width. Assuming that the arity of predicates is bounded, we show that polynomial-size nonrecursive Datalog rewritings can be constructed and executed in (i) LOGCFL for OMQs with ontologies of bounded existential ...
Added: September 18, 2017
Zakharyaschev M., Kikot S., Bienvenu M. et al., , in: Proceedings of the 30th International Workshop on Description Logics, Montpellier, France, July 18-21, 2017.: Aachen: CEUR Workshop Proceedings, 2017..
We discuss the parameterised complexity of answering tree-shaped ontology-mediated queries (OMQs) in OWL2QL under various restrictions on their ontologies and conjunctive queries (CQs). In particular, we construct an ontology τ such that answering OMQs (τ, q) with tree-shaped CQs q is W[1]- hard if the number of leaves in q is regarded as the parameter. ...
Added: September 18, 2017
Rubtsov A. A., Vyalyi M., , in: Developments in Language Theory 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings.: Cham: Springer, 2017. P. 332–344.
We consider a computational model which is known as set automata. The set automata are one-way finite automata with an additional storage---the set. There are two kinds of set automata---the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by M. Kutrib, A. Malcher, M. Wendlandt in ...
Added: September 5, 2017
Cham: Springer, 2017.
The 21st International Conference on Developments in Language Theory (DLT 2017) was organized by the Department of Mathematics of the University of Liège, Belgium, during August 7–11, 2017.
The DLT conference series is one of the major international conference series in language theory and related areas. The DLT conference was established by G. Rozenberg and A. ...
Added: September 5, 2017
Vyalyi M., Rubtsov A. A., Проблемы передачи информации 2015 Т. 51 № 4 С. 47–59
We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance ...
Added: February 14, 2016
Rubtsov A. A., Vyalyi M., , in: Descriptional Complexity of Formal SystemsVol. 9118.: Switzerland: Springer, 2015. P. 256–267.
We investigate regular realizability (RR) problems, which are the prob- lems of verifying whether intersection of a regular language – the input of the problem – and fixed language called filter is non-empty. In this pa- per we focus on the case of context-free filters. Algorithmic complexity of the RR problem is a very coarse ...
Added: August 25, 2015