Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 636228)
Контекстум
Электро-2024
Вестник Московского университета. Серия 1. Математика. Механика  / №1 2016

О СЛОВАХ, ИЗБЕГАЮЩИХ КВАДРАТОВ С ОДНОЙ ВОЗМОЖНОЙ ОШИБКОЙ ЗАМЕЩЕНИЯ (60,00 руб.)

0   0
Первый авторКотляров
Страниц5
ID366822
АннотацияСтатья посвящена некоторым вопросам, связанным с существованием периодических структур в словах из формальных языков. Рассматриваются квадраты, т.е. фрагменты вида хх, где х — произвольное слово, и квадраты с одной ошибкой — фрагменты вида ху, где слово х отличается от слова у на одну букву. Устанавливается существование сколь угодно длинных слов, не содержащих квадратов с длиной больше lо и квадратов с одной ошибкой и длиной больше l1 в зависимости от натуральных чисел lо и l1. Для всех возможных пар li > lо найден минимальный алфавит, над которым можно построить такое слово.
УДК519.765
Котляров, Н.В. О СЛОВАХ, ИЗБЕГАЮЩИХ КВАДРАТОВ С ОДНОЙ ВОЗМОЖНОЙ ОШИБКОЙ ЗАМЕЩЕНИЯ / Н.В. Котляров // Вестник Московского университета. Серия 1. Математика. Механика .— 2016 .— №1 .— С. 48-52 .— URL: https://rucont.ru/efd/366822 (дата обращения: 23.05.2024)

Предпросмотр (выдержки из произведения)

Рассматриваются квадраты, т.е. фрагменты вида хх, где х — произвольное слово, и квадраты с одной ошибкой — фрагменты вида ху, где слово х отличается от слова у на одну букву. <...> Устанавливается существование сколь угодно длинных слов, не содержащих квадратов с длиной больше и квадратов с одной ошибкой и длиной больше l1 в зависимости от натуральных чисел и l1. <...> Для всех возможных пар li > найден минимальный алфавит, над которым можно построить такое слово.! <...>