The Chvátal–Sankoff problem as a problem of symbolic dynamics

Пусть даны две равномерно случайные двоичные строки равной длины. Математическое ожидание длины их наибольшей общей подпоследовательности (longest common subsequence, LCS) асимптотически пропорционально длине строк. Естественным образом возникает проблема нахождения коэффициента этой пропорциональности $\gamma$, то есть предела нормализованной длины LCS двух случайных двоичных строк длины $n \to \infty$. Эта проблема была впервые сформулирована Хваталом (Chvátal) и Санкоффом (Sankoff) в 1975 г. и до сих пор не решена. Она имеет отношение к самым разнообразным областям исследований: от комбинаторики и анализа алгоритмов до теории кодирования и вычислительной биологии. В предыдущей статье мы использовали методы статистической механики, а также известные результаты о комбинаторной структуре LCS, чтобы установить связь между константой $\gamma$ и параметрами некоторого стохастического процесса взаимодействия частиц. В данной статье, мы дополняем этот анализ формулировкой задачи на языке символической динамики и клеточных автоматов, и приводим некоторые предварительные результаты вычислительного эксперимента, выполненного с целью улучшить существующие численные оценки для $\gamma$. Мы также указываем на ошибку в предыдущей статье, которая отменяет некоторые заявленные в ней результаты относительно свойств $\gamma$. Библ. – 57 назв.