Войти / Регистрация
Корзина

  • Ваша корзина пуста
Войти / Регистрация
Корзина

  • Ваша корзина пуста

Статья «О существовании сколь угодно длинных слов, не содержащих квадратов с одной возможной ошибкой замещения, "Дискретная математика"»

Авторы:
  • Котляров Н В1
стр. 56-72
Платно
1 Московский государственный университет имени М.В. Ломоносова
Аннотация:
Данная статья посвящена вопросам, связанным с существованием периодических структур в словах из формальных языков. Рассматриваются квадраты, то есть фрагменты вида , где произвольное слово, и квадраты с одной ошибкой, то есть фрагменты вида , где слово отличается от слова ровно на одну букву. В данной статье изучаются условия существования сколь угодно длинных слов, не содержащих квадратов с длиной больше и квадратов с одной ошибкой и длиной больше в зависимости от натуральных чисел и . Для всех возможных пар найден минимальный алфавит, над которым можно построить такое слово. Работа выполнена при поддержке РФФИ, проект N 14-01-00598 (Вопросы синтеза, сложности и контроля управляющих систем), и программы фундаментальных исследований ОМН РАН Алгебраические и комбинаторные методы математической кибернетики и информационные системы нового поколения (проект Задачи оптимального синтеза управляющих систем ). Также поддержка была оказана ИППИ РАН за счет гранта Российского научного фонда (проект № 14-50-00150).

Архивные статьи (2015 год и ранее) доступны для ознакомления бесплатно, для скачивания их необходимо приобрести. Для просмотра материалов необходимо зарегистрироваться и авторизоваться на сайте.

Чтобы приобрести доступ к материалу для юридического лица, пожалуйста, свяжитесь с администрацией портала с помощью формы обратной связи либо по электронному адресу libnauka@naukaran.com.  

Действия с материалами доступны только авторизованным пользователям.