?
Regular Realizability Problems and Context- Free Languages
P. 256-267.
Rubtsov A. A., Vyalyi M.
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 measure of context-free languages com- plexity. This characteristic is compatible with rational dominance. We present examples of P-complete RR problems as well as examples of RR problems in the class NL. Also we discuss RR problems with context- free filters that might have intermediate complexity. Possible candidates are the languages with polynomially bounded rational indices.
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, Proceedings. Vol. 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
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 : 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
Rubtsov A. A., , in : Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. : Cham : Springer, 2018. P. 553-565.
We present a new structural lemma for deterministic con- text free languages. From the first sight, it looks like a pumping lemma, because it is also based on iteration properties, but it has significant distinctions that makes it much easier to apply. The structural lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), ...
Added: September 12, 2018
Rubtsov A. A., На правах рукописи, 2016
В диссертации исследуется задача регулярной реализуемости, которая состоит в проверке пересечения фиксированного языка (параметра задачи) с регулярным языком на входе задачи. Основная часть работа посвящена исследованию вычислительной сложности задачи для КС-фильтров. ...
Added: November 1, 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
Rubtsov A. A., В кн. : Сборник научных трудов МФТИ "Модели и методы обработки информации". : Долгопрудный : МФТИ, 2016. С. 67-74.
В работе исследуются комбинаторные свойства детерминированных контекстно-свободных языков. Получена новая комбинаторная лемма, схожая по типу с леммами о накачке для КС-языков, а также получены комбинаторные свойства, следующие из модифицированной известной техники, опирающейся на Колмогоровскую сложность. ...
Added: October 20, 2018
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
Vyalyi M., Rubtsov A. A., Дискретный анализ и исследование операций 2012
Работа посвящена двум алгоритмическим задачам, связанным с анализом поведения конечного автомата при чтении сверхслова (бесконечной последовательности): достигает ли автомат принимающего состояния и достигает ли он принимающего состояния бесконечно часто. Первая задача возникает при анализе моделей обобщённого недетерминизма, а вторая – при анализе разрешимости монадических теорий второго порядка. Получены новые условия разрешимости для этих задач. Доказано, что всякая задача ...
Added: October 17, 2014
Rubtsov Alexander, , in : Abstracts of Reports and other materials of the 7th School "Computer Science Days in Ekaterinburg". : Ekaterinburg : Ural Fedearal University, 2014. P. 25-27.
Added: October 17, 2014
Rubtsov A. A., Vyalyi M., Information and Computation 2019
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 ...
Added: October 22, 2018
Rubtsov A. A., В кн. : Труды IX Международной конференции "Дискретные модели в теории управляющих систем". : М. : МАКС Пресс, 2015. С. 207-210.
В работе исследована вычислительная сила детерминированных и недетерминированных автомтаов со словарём. ...
Added: August 25, 2015
Springer, 2020
Added: October 22, 2018
Sergei Valentinovich Fedorenko, IEEE Access 2023 Vol. 11 P. 62771-62779
The novel methods for binary discrete Fourier transform (DFT) computation over the finite field have been proposed. The methods are based on a binary trace calculation over the finite field and use the cyclotomic DFT. The direct DFT computational complexity has been reduced due to using the binary trace function over the finite field and ...
Added: July 19, 2023
Rubtsov A. A., В кн. : Труды 56-й научной конференции МФТИ: Всероссийской научной конференции «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе» , Всероссийской молодежной научно-инновационной конференции «Физико-математические науки: актуальные проблемы и их решения». Т. 1: Управление и прикладная математика.: Долгопрудный : МФТИ, 2013. С. 128-130.
В работе исследована инвариантная характеристика автоматных преобразований (преобразований, заданных deterministic finite state transducer ) — функция высоты. ...
Added: October 17, 2014
Rubtsov A. A., В кн. : Труды 57-й научной конференции МФТИ — Всероссийской научной конференции с международным участием «Актуальные проблемы фундаментальных и прикладных наук в области физики», Всероссийской молодежной научной конференции с международным участием «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе». Т. 1: Управление и прикладная математика.: М. : МФТИ, 2014. С. 123-125.
В работе приведены примеры различных языков, распознаваемых автоматами со словарём и исследована их вычислительная сложность. ...
Added: August 25, 2015
[б.и.], 2016
Added: September 18, 2017
Rubtsov A. A., В кн. : Труды X международной конференции "Дискретные модели в теории управляющих систем". Москва и Подмосковье, 23-25 мая 2018 г. : М. : МАКС Пресс, 2018. С. 234-237.
Иерархия Хомского — хорошо известная иерархия формальных языков, основанная на формальных грамматиках. Однако эта иерархия покрывает лишь четыре класса формальных языков: регулярные, контекстно-свободные, контекстно-зависимые и рекурсивно-перечислимые.
В этой работе мы обобщаем понятие формальной грамматики. ...
Added: October 20, 2018
Cham : Springer, 2018
This volume of Lecture Notes in Computer Science contains the papers presented at the 22nd International Conference on Developments in Language Theory (DLT 2018) organized by the Algorithmic “Oritatami” Self-Assembly Laboratory as part of the 100th Anniversary Commemorative Events of University of Electro-Communications (UEC) in Fuchu, Tokyo, Japan, during September 10–14, 2018.
The DLT conference series is one ...
Added: September 12, 2018
Rubtsov A. A., В кн. : Проблемы теоретической кибернетики. Материалы XVII международной конференции. : Каз. : Отечество, 2014. С. 246-248.
В работе исследуется задача регулярной реализуемости: алгоритмическая задача проверки непустоты пересечения регулярного языка на входе и фиксированного языка-фильтра, который является параметром задачи, — в случае контекстно-свободного фильтра. ...
Added: October 17, 2014
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
Aleskerov F. T., Meshcheryakova N., Shvydun S. et al., , in : 6th International Conference on Computers Communications and Control (ICCCC) 2016. : Oradea : Agora University, 2016. P. 118-123.
The problem of quick detection of central nodes in large networks is studied. There are many measures that allow to evaluate a topological importance of nodes of the network. Unfortunately, most of them cannot be applied to large networks due to their high computational complexity. However, if we narrow the initial network and apply these ...
Added: June 8, 2016