|
Записки научных семинаров ПОМИ, 2023, том 528, страницы 214–237
(Mi znsl7411)
|
|
|
|
The Chvátal–Sankoff problem as a problem of symbolic dynamics
[Проблема Хватала–Санкоффа как задача символической динамики]
A. Tiskinab a Department of Mathematics and Computer Science, St. Petersburg State University
b St. Petersburg Electrotechnical University “LETI”
Аннотация:
Пусть даны две равномерно случайные двоичные строки равной длины. Математическое ожидание длины их наибольшей общей подпоследовательности (longest common subsequence, LCS) асимптотически пропорционально длине строк. Естественным образом возникает проблема нахождения коэффициента этой пропорциональности $\gamma$, то есть предела нормализованной длины LCS двух случайных двоичных строк длины $n \to \infty$. Эта проблема была впервые сформулирована Хваталом (Chvátal) и Санкоффом (Sankoff) в 1975 г. и до сих пор не решена. Она имеет отношение к самым разнообразным областям исследований: от комбинаторики и анализа алгоритмов до теории кодирования и вычислительной биологии. В предыдущей статье мы использовали методы статистической механики, а также известные результаты о комбинаторной структуре LCS, чтобы установить связь между константой $\gamma$ и параметрами некоторого стохастического процесса взаимодействия частиц. В данной статье, мы дополняем этот анализ формулировкой задачи на языке символической динамики и клеточных автоматов, и приводим некоторые предварительные результаты вычислительного эксперимента, выполненного с целью улучшить существующие численные оценки для $\gamma$. Мы также указываем на ошибку в предыдущей статье, которая отменяет некоторые заявленные в ней результаты относительно свойств $\gamma$. Библ. – 57 назв.
Ключевые слова:
случайные строки, наибольшая общая подпоследовательность, проблема Хватала–Санкоффа, процессы взаимодействия частиц, символическая динамика, клеточные автоматы.
Поступило: 01.12.2023
Образец цитирования:
A. Tiskin, “The Chvátal–Sankoff problem as a problem of symbolic dynamics”, Теория представлений, динамические системы, комбинаторные методы. XXXV, Зап. научн. сем. ПОМИ, 528, ПОМИ, СПб., 2023, 214–237
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl7411 https://www.mathnet.ru/rus/znsl/v528/p214
|
|