Как решать задачи на строках, если вместо текста на вход получена лишь программа порождающяя этот текст? Можно ли это сделать быстрее, чем запустив программу?

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

Получены следующие оригинальные результаты: кубический алгоритм проверки равенста строк, порожденных прямолинейными программами, O(n^2*m) алгоритм для поиска подстрок, алгоритмы для нахождения периодов, покрытий (covers), и таблицы отпечатков (fingerprint table). С другой стороны, нахождение расстояния Хемминга и поиск разряженных подпоследовательностей является NP-трудным.