?
A Structural Lemma for Deterministic Context-Free Languages
P. 553-565.
Рубцов А. А.
Ключевые слова: колмогоровская сложностьKolmogorov complexityтеория автоматовautomata theoryформальные языкиformal languages
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Рубцов А. А., Вялый М. Н., , in : Descriptional Complexity of Formal Systems. Vol. 9118.: Switzerland : Springer, 2015. P. 256-267.
Добавлено: 25 августа 2015 г.
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 ...
Добавлено: 12 сентября 2018 г.
Рубцов А. А., Вялый М. Н., , 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.
Добавлено: 21 июня 2018 г.
Рубцов А. А., На правах рукописи, 2016
В диссертации исследуется задача регулярной реализуемости, которая состоит в проверке пересечения фиксированного языка (параметра задачи) с регулярным языком на входе задачи. Основная часть работа посвящена исследованию вычислительной сложности задачи для КС-фильтров. ...
Добавлено: 1 ноября 2018 г.
Рубцов А. А., , in : Proceedings of Language and Automata Theory and Applications 2020. : Springer, 2020.
Добавлено: 19 октября 2017 г.
Авдошин С. М., Набебин А. А., М. : ДМК Пресс, 2018
Книга содержит основные сведения из формально-логических систем. Это функции алгебры логики (булевы функции), теорема Поста о функциональной полноте, k-значные логики, производные булевых функций, аксиоматические исчисления высказываний, предикатов, секвенций, резолюций и язык программирования Пролог. Рассматриваются монадическая логика, конечные автоматы и представимые ими языки, темпоральная логика, аксиоматический язык программирования OBJ3. В основу книги положен многолетний опыт преподавания ...
Добавлено: 2 декабря 2017 г.
Рубцов А. А., В кн. : Сборник научных трудов МФТИ "Модели и методы обработки информации". : Долгопрудный : МФТИ, 2016. С. 67-74.
В работе исследуются комбинаторные свойства детерминированных контекстно-свободных языков. Получена новая комбинаторная лемма, схожая по типу с леммами о накачке для КС-языков, а также получены комбинаторные свойства, следующие из модифицированной известной техники, опирающейся на Колмогоровскую сложность. ...
Добавлено: 20 октября 2018 г.
Switzerland : Springer International Publishing, 2021
Добавлено: 28 сентября 2021 г.
Милованов А. С., , in : Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015. Vol. 9139.: Springer, 2015. P. 339-349.
Добавлено: 27 июня 2016 г.
Милованов А. С., Theory of Computing Systems 2017 Vol. 61 No. 2 P. 521-535
Algorithmic statistics is a part of algorithmic information theory (Kolmogorov complexity theory) that studies the following task: given a finite object x (say, a binary string), find an `explanation' for it, i.e., a simple finite set that contains x and where x is a `typical element'. Both notions (`simple' and `typical') are defined in terms ...
Добавлено: 27 июня 2016 г.
Shen A., Верещагин Н. К., , in : Computability and Complexity. : Berlin : Springer, 2017. P. 669-737.
Добавлено: 26 октября 2018 г.
Бабаш А. В., , in : Proceedings of the 10th International Scientific and Practical Conference named after A. I. Kitov "Information Technologies and Mathematical Methods in Economics and Management (IT&MM-2020)"/, Moscow, Russia, October 15-16, 2020. Vol. 2830.: CEUR Workshop Proceedings, 2021. P. 337-359.
A trapdoor cipher is a cipher whose algorithm contains some hidden structure (a trapdoor) providing the existence of a subliminal information channel. In cryptographic practice, there could be situations when a constructed cipher may contain some critical defect (a trapdoor) whose identification can significantly weaken the cryptographic strength of this cipher. In this paper, we ...
Добавлено: 2 ноября 2021 г.
Bienvenu L., Muchnik A., Shen A. и др., / Cornell University. Series math "arxiv.org". 2012. No. 1204.0201.
Добавлено: 14 декабря 2013 г.
Баувенс Б. Ф., , in : 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Vol. 154: Leibniz International Proceedings in Informatics (LIPIcs).: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. P. 46:1-46:14.
Добавлено: 20 марта 2020 г.
Рубцов А. А., В кн. : Труды 57-й научной конференции МФТИ — Всероссийской научной конференции с международным участием «Актуальные проблемы фундаментальных и прикладных наук в области физики», Всероссийской молодежной научной конференции с международным участием «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе». Т. 1: Управление и прикладная математика.: М. : МФТИ, 2014. С. 123-125.
В работе приведены примеры различных языков, распознаваемых автоматами со словарём и исследована их вычислительная сложность. ...
Добавлено: 25 августа 2015 г.
Баувенс Б. Ф., Блинников И. А., , in : Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings. Vol. 12159.: Springer, 2020. P. 130-141.
Добавлено: 5 февраля 2021 г.
М. : Московский государственный технический университет им. Н.Э. Баумана, 2023
Сборник содержит тезисы докладов, представленных на международной научно-технической конференции "Безопасные информационные технологии" (БИТ-2023), проходившей 1-2 ноября 2023 г. в Москве в МГТУ им. Н.Э.Баумана.
Тезисы публикуются в редакции научных руководителей или в авторской редакции при наличии ученой степени. ...
Добавлено: 16 февраля 2024 г.
Милованов А. С., , in : Computer Science – Theory and Applications: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings. : Springer, 2021. Ch. 17. P. 283-295.
Добавлено: 11 августа 2021 г.
Милованов А. С., , in : 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) Leibniz International Proceedings in Informatics (LIPIcs). : Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2016. Ch. 54. P. 1-13.
Добавлено: 27 июня 2016 г.
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. ...
Добавлено: 5 сентября 2017 г.
Баувенс Б. Ф., Shen A., Journal of Symbolic Logic 2013 Vol. 79 No. 2 P. 620-632
Добавлено: 2 октября 2015 г.
Милованов А. С., , in : Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017). Vol. 10304.: Luxemburg : Springer, 2017. P. 232-244.
Добавлено: 15 октября 2017 г.