Сравнение детерминированных и случайных строк

Длина наибольшей общей подпоследовательности (longest common subsequence, LCS) пары строк - естественная мера их схожести, возникающая в самых разнообразных областях математики, теоретической и практической информатики и биоинформатики. В случае, когда заданные строки являются равномерно случайными бинарными строками равной длины, нахождение асимптотики матожидания длины их LCS - открытая проблема, впервые сформулированная Хваталом и Санковым в 1975 году. В докладе будут представлены результаты автора о комбинаторной структуре LCS и ее неожиданной связи с алгеброй полугрупп, а также рассказано об изучении проблемы Хватала-Санкова методами статистической механики и символической динамики.