?
Исследование задачи регулярной реализуемости для контекстно-свободных языков.
С. 246-248.
Рубцов А. А.
В работе исследуется задача регулярной реализуемости: алгоритмическая задача проверки непустоты пересечения регулярного языка на входе и фиксированного языка-фильтра, который является параметром задачи, — в случае контекстно-свободного фильтра.
В книге
Каз. : Отечество, 2014
Рубцов А. А., На правах рукописи, 2016
В диссертации исследуется задача регулярной реализуемости, которая состоит в проверке пересечения фиксированного языка (параметра задачи) с регулярным языком на входе задачи. Основная часть работа посвящена исследованию вычислительной сложности задачи для КС-фильтров. ...
Добавлено: 1 ноября 2018 г.
Вялый М. Н., Рубцов А. А., Дискретный анализ и исследование операций 2012
Работа посвящена двум алгоритмическим задачам, связанным с анализом поведения конечного автомата при чтении сверхслова (бесконечной последовательности): достигает ли автомат принимающего состояния и достигает ли он принимающего состояния бесконечно часто. Первая задача возникает при анализе моделей обобщённого недетерминизма, а вторая – при анализе разрешимости монадических теорий второго порядка. Получены новые условия разрешимости для этих задач. Доказано, что всякая задача ...
Добавлено: 17 октября 2014 г.
Рубцов А. А., В кн. : Труды 56-й научной конференции МФТИ: Всероссийской научной конференции «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе» , Всероссийской молодежной научно-инновационной конференции «Физико-математические науки: актуальные проблемы и их решения». Т. 1: Управление и прикладная математика.: Долгопрудный : МФТИ, 2013. С. 128-130.
В работе исследована инвариантная характеристика автоматных преобразований (преобразований, заданных deterministic finite state transducer ) — функция высоты. ...
Добавлено: 17 октября 2014 г.
Рубцов А. А., Вялый М. Н., , in : Descriptional Complexity of Formal Systems. Vol. 9118.: Switzerland : Springer, 2015. P. 256-267.
Добавлено: 25 августа 2015 г.
Рубцов А. А., Вялый М. Н., , 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 г.
Бирюков И. И., М. : МГИЭМ, 2010
Курс «Теория автоматов» является одним из фундаментальных курсов для дальнейшего изучения всех дисциплин, связанных с аппаратной частью ЦВМ. Данный курс формировался постепенно, складываясь из предшествующих ему курсов: «Арифметические и логические основы цифровых автоматов» и «Прикладная теория цифровых автоматов». Автор долгое время читал предыдущие курсы и в настоящее время читает этот курс. За время чтения лекций ...
Добавлено: 25 февраля 2015 г.
Вялый М. Н., Рубцов А. А., Проблемы передачи информации 2015 Т. 51 № 4 С. 47-59
Рассматриваются задачи регулярной реализуемости, которые состоят в проверке непустоты пересечения регулярного языка на входе задачи и фиксированного языка (фильтра), который явля- ется параметром задачи. В данной работе изучается алгоритмиче- ская сложность задач регулярной реализуемости для контекстно- свободных фильтров. Эта характеристика согласована с отноше- нием рационального доминирования на КС-языках. Однако, как доказано в работе, она более ...
Добавлено: 14 февраля 2016 г.
Серебряков В. А., Гончар Д. Р., Рубцов А. А. и др., МФТИ, 2017
Содержит программу, список литературы и задачи одноимённого курса, читаемого студентам факультета управления и прикладной математики МФТИ (ГУ). Задачи могут быть использованы в качестве упражнений на семинарских занятиях, заданий, экзаменационного материала, а также при самостоятельном освоениии курса. ...
Добавлено: 20 октября 2017 г.
Бирюков И. И., М. : МГИЭМ, 2012
Курс «Теория автоматов» является одним из фундаментальных курсов для дальнейшего изучения всех дисциплин, связанных с аппаратной частью ЦВМ. Данный курс формировался постепенно, складываясь из предшествующих ему курсов: «Арифметические и логические основы цифровых автоматов» и «Прикладная теория цифровых автоматов». Автор долгое время читал предыдущие курсы и в настоящее время читает этот курс. За время чтения лекций ...
Добавлено: 25 февраля 2015 г.
Бирюков И. И., М. : МГИЭМ, 2010
Курс «Теория автоматов» является одним из фундаментальных курсов для дальнейшего изучения всех дисциплин, связанных с аппаратной частью ЦВМ. Данный курс формировался постепенно, складываясь из предшествующих ему курсов: «Арифметические и логические основы цифровых автоматов» и «Прикладная теория цифровых автоматов». Автор долгое время читал предыдущие курсы и в настоящее время читает этот курс. За время чтения лекций ...
Добавлено: 25 февраля 2015 г.
Рубцов А. А., , in : Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. : Cham : Springer, 2018. P. 553-565.
Добавлено: 12 сентября 2018 г.
Рубцов А. А., В кн. : Труды 57-й научной конференции МФТИ — Всероссийской научной конференции с международным участием «Актуальные проблемы фундаментальных и прикладных наук в области физики», Всероссийской молодежной научной конференции с международным участием «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе». Т. 1: Управление и прикладная математика.: М. : МФТИ, 2014. С. 123-125.
В работе приведены примеры различных языков, распознаваемых автоматами со словарём и исследована их вычислительная сложность. ...
Добавлено: 25 августа 2015 г.
Рубцов А. А., В кн. : Труды IX Международной конференции "Дискретные модели в теории управляющих систем". : М. : МАКС Пресс, 2015. С. 207-210.
В работе исследована вычислительная сила детерминированных и недетерминированных автомтаов со словарём. ...
Добавлено: 25 августа 2015 г.