Записки научных семинаров ПОМИ
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Записки научных семинаров ПОМИ, 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 назв.
Ключевые слова: случайные строки, наибольшая общая подпоследовательность, проблема Хватала–Санкоффа, процессы взаимодействия частиц, символическая динамика, клеточные автоматы.
Финансовая поддержка Номер гранта
Российский научный фонд 22-21-00669
This work was supported by the Russian Science Foundation under grant no. 22-21-00669, https://www.rscf.ru/en/project/22-21-00669/.
Поступило: 01.12.2023
Тип публикации: Статья
УДК: 519.119
Язык публикации: английский
Образец цитирования: A. Tiskin, “The Chvátal–Sankoff problem as a problem of symbolic dynamics”, Теория представлений, динамические системы, комбинаторные методы. XXXV, Зап. научн. сем. ПОМИ, 528, ПОМИ, СПб., 2023, 214–237
Цитирование в формате AMSBIB
\RBibitem{Tis23}
\by A.~Tiskin
\paper The Chv\'atal--Sankoff problem as a problem of symbolic dynamics
\inbook Теория представлений, динамические системы, комбинаторные методы.~XXXV
\serial Зап. научн. сем. ПОМИ
\yr 2023
\vol 528
\pages 214--237
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl7411}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/znsl7411
  • https://www.mathnet.ru/rus/znsl/v528/p214
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024