Докладчик: Андрей Петрович Немытых (ИПС им. А.К. Айламазяна РАН)
Дата: 16 ноября 2017
Время: 14:00
Место: зал ученого совета ИПС
Аннотация: При анализе (например, верификации) программ, манипулирующих строками символов, возникают уравнения в конечнопорожденной свободной полугруппе с единицей (или, что то же самое, уравнения в словах).
Пусть фиксирован некоторый конечный алфавит символов-констант A и алфавит символов переменных X, область допустимых значений которых есть множество слов в алфавите A. Рассмотрим два произвольных слова w_1, w_2 в алфавите A u X (объединение двух множеств) и поставим между ними знак равенства:
w_1 = w_2 . Получили конкретное уравнение в словах. В задаче требуется найти все значения переменных, входящих в w_1 или w_2, такие что, после подстановки этих значений вместо соответствующих переменных в уравнение w_1 = w_2, это уравнение превращается в графическое равенство.
А.А. Марков (1954 г.) предложил алгоритм, распознающий существование решений уравнений в словах с двумя переменными и поставил задачу доказательства неразрешимости аналогичной задачи с произвольным числом (n-) переменных.
Ю.И. Хмелевский (1967 г.) построил алгоритм, распознающий существует ли решение уравнение в словах с тремя переменными и перечисляющий решения этого уравнения, если они существуют.
Г.С. Маканин (1977 г.) описал нетривиальный алгоритм, перечисляющий все решения данного уравнения в словах с n переменными.
Алгоритм Маканина является очень сложным. Он в течение долгого времени интенсивно изучался многими авторами.
A. Jez (2014-2015 гг.) предложил недетерминированный алгоритм решения уравнений в словах, основанный на оригинальных идеях (см.
https://arxiv.org/pdf/1203.3705v3.pdf). Алгоритм Jez-а существенно проще алгоритма Маканина и требуют дальнейшего изучения.
Докладчик расскажет о некоторых:
(1) понятиях алгоритма Jez-а и алгоритма Маканина;
(2) классах уравнений в свободном моноиде конечного ранга, для которых существуют простые алгоритмы решения;
и продемонстрирует алгоритм Jez-а на простейших примерах.
