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

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

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



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Дискрет. матем., 2015, том 27, выпуск 2, страницы 56–72 (Mi dm1325)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

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

Н. В. Котляровab

a МГУ им. М. В. Ломоносова
b Институт проблем передачи информации им. А.А. Харкевича РАН

Аннотация: Данная статья посвящена вопросам, связанным с существованием периодических структур в словах из формальных языков. Рассматриваются квадраты, то есть фрагменты вида $xx$, где $x$ — произвольное слово, и квадраты с одной ошибкой, то есть фрагменты вида $xy$, где слово $x$ отличается от слова $y$ ровно на одну букву. В данной статье изучаются условия существования сколь угодно длинных слов, не содержащих квадратов с длиной больше $l_0$ и квадратов с одной ошибкой и длиной больше $l_1$ в зависимости от натуральных чисел $l_0$ и $l_1$. Для всех возможных пар $l_1\geq l_0$ найден минимальный алфавит, над которым можно построить такое слово.
Работа выполнена при поддержке РФФИ, проект N 14-01-00598 (Вопросы синтеза, сложности и контроля управляющих систем), и программы фундаментальных исследований ОМН РАН “Алгебраические и комбинаторные методы математической кибернетики и информационные системы нового поколения” (проект “Задачи оптимального синтеза управляющих систем”). Также поддержка была оказана ИППИ РАН за счет гранта Российского научного фонда (проект № 14-50-00150).

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


DOI: https://doi.org/10.4213/dm1325

Полный текст: PDF файл (467 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Discrete Mathematics and Applications, 2015, 25:6, 345–357

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.765
Статья поступила: 17.12.2014

Образец цитирования: Н. В. Котляров, “О существовании сколь угодно длинных слов, не содержащих квадратов с одной возможной ошибкой замещения”, Дискрет. матем., 27:2 (2015), 56–72; Discrete Math. Appl., 25:6 (2015), 345–357

Цитирование в формате AMSBIB
\RBibitem{Kot15}
\by Н.~В.~Котляров
\paper О существовании сколь угодно длинных слов, не содержащих квадратов с одной возможной ошибкой замещения
\jour Дискрет. матем.
\yr 2015
\vol 27
\issue 2
\pages 56--72
\mathnet{http://mi.mathnet.ru/dm1325}
\crossref{https://doi.org/10.4213/dm1325}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3468391}
\elib{https://elibrary.ru/item.asp?id=24073693}
\transl
\jour Discrete Math. Appl.
\yr 2015
\vol 25
\issue 6
\pages 345--357
\crossref{https://doi.org/10.1515/dma-2015-0033}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000366856000003}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84949954968}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1325
  • https://doi.org/10.4213/dm1325
  • http://mi.mathnet.ru/rus/dm/v27/i2/p56

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Н. В. Котляров, “О существовании слов над трехбуквенным алфавитом, не содержащих квадратов с ошибками замещения”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2018, № 3, 8–16  mathnet  mathscinet  zmath; N. V. Kotlyarov, “Existence of words over a three-letter alphabet not containing squares with errors of replacing”, Moscow University Mathematics Bulletin, 73:3 (2018), 90–97  crossref  isi
    2. Н. В. Котляров, “О существовании слов над двухбуквенным алфавитом, не содержащих квадратов с ошибками замещения”, Дискрет. матем., 30:2 (2018), 37–54  mathnet  crossref  elib; N. V. Kotlyarov, “Existence of words over a binary alphabet free from squares with mismatches”, Discrete Math. Appl., 29:3 (2019), 175–188  crossref  isi
  • Дискретная математика
    Просмотров:
    Эта страница:215
    Полный текст:61
    Литература:25
    Первая стр.:37
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021