Михаил Николаевич Вялый

Решение уравнений в словах

Продолжительность: 4 занятия.

Слово - последовательность символов из некоторого алфавита. Самая простая операция со словами - конкатенация, то есть дописывание одного слова после другого. Левая и правая часть уравнения в словах составляются конкатенациями переменных, которые предполагаются словами, и констант, которые принадлежат алфавиту.

Существует ли алгоритм решения любого уравнения в словах? Ответ положительный.

Эта задача оказалась не очень простой. В последнее время появились более простые(но, по-прежнему, нетривиальные) решения этой задачи. В данном цикле занятий будет разобран пример такого алгоритма и (возможно) будет также разобран гораздо более эффективный алгоритм для решения уравнения в словах, когда заранее предписаны длины словарных переменных.

Organization Committee e-mail:
dubna@mccme.ru