?
On the succinctness of query rewriting over shallow ontologies
Ch. 57. P. 57.1–57.10.
Kikot S., Kontchakov R., Podolskii V., Захарьящев М. В.
Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity
Bienvenu M., Kikot S., Kontchakov R. и др., Journal of the ACM 2018 Vol. 65 No. 5 P. 28:1–28:51
Добавлено: 16 октября 2018 г.
Подольская О. В., В кн.: Материалы X молодежной научной школы по дискретной математике и ее приложениям.: М.: Издательство ИПМ РАН, 2015. С. 56–58.
Доказано, что сложность реализации произвольной симметрической булевой функции f от n переменных для f не равной тождественно единице при реализации схемами в базисе антицепных функций, т.е. функций, принимающих значение 1 лишь на попарно несравнимых наборах, равна min(k(f),n-k(f)+2), где k(f) - количество слоев, на которых функция f равна 1. ...
Добавлено: 11 января 2016 г.
Максимов Ю. В., / Series arXiv "math". 2015.
Добавлено: 30 октября 2015 г.
Granin S., Максимов Ю. В., / Series arXiv "math". 2015.
Добавлено: 30 октября 2015 г.
Максимов Ю. В., / Series arXiv "math". 2015.
Добавлено: 30 октября 2015 г.
Максимов Ю. В., Computational Mathematics and Mathematical Physics 2015 Vol. 49 No. 7 P. 1327
Добавлено: 30 октября 2015 г.
Максимов Ю. В., Doklady Mathematics 2012 Vol. 86 No. 3 P. 854–856
Добавлено: 30 октября 2015 г.
Максимов Ю. В., Doklady Mathematics 2012 Vol. 86 No. 1 P. 480–482
Добавлено: 30 октября 2015 г.
Максимов Ю. В., Computational Mathematics and Mathematical Physics 2013 Vol. 53 No. 9 P. 1569–1588
Добавлено: 30 октября 2015 г.
Максимов Ю. В., Computational Mathematics and Mathematical Physics 2015 Vol. 55 No. 7 P. 1242–1255
Добавлено: 30 октября 2015 г.
Подольская О. В., В кн.: Материалы IX молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 сентября 2013 г.).: М.: Издательство ИПМ РАН, 2013. С. 97–100.
В работе рассматривается задача о сложности реализации булевых функций схемами из функциональных элементов в бесконечном полном базисе, который состоит из всевозможных булевых функций, принимающих единичное значение лишь на попарно несравнимых наборах. Известны нижние оценки порядка $\sqrt n$ для сложности реализации линейной функции, функции голосования и почти всех булевых функций от $n$ переменных. Установлена верхняя оценка ...
Добавлено: 31 мая 2015 г.
Gottlob G., Kikot S., Kontchakov R. и др., Artificial Intelligence 2014 Vol. 213 P. 42–59
Добавлено: 24 марта 2015 г.
Kikot S., Kontchakov R., Подольский В. В. и др., , in: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).: NY: ACM, 2014. P. 1–10.
Добавлено: 20 октября 2014 г.
Gottlob G., Kikot S., Kontchakov R. и др., Artificial Intelligence 2014 Vol. 213 P. 42–59
We give a solution to the succinctness problem for the size of first-order rewritings of conjunctive queries in ontologybased data access with ontology languages such as OWL2QL, linear Datalog and sticky Datalog. We show that positive existential and nonrecursive datalog rewritings, which do not use extra non-logical symbols (except for intensional predicates in the case ...
Добавлено: 20 октября 2014 г.