|
Эта публикация цитируется в 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).
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/dm1325https://doi.org/10.4213/dm1325 http://mi.mathnet.ru/rus/dm/v27/i2/p56
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Н. В. Котляров, “О существовании слов над трехбуквенным алфавитом, не содержащих квадратов с ошибками замещения”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2018, № 3, 8–16
  ; 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 -
Н. В. Котляров, “О существовании слов над двухбуквенным алфавитом, не содержащих квадратов с ошибками замещения”, Дискрет. матем., 30:2 (2018), 37–54 ; N. V. Kotlyarov, “Existence of words over a binary alphabet free from squares with mismatches”, Discrete Math. Appl., 29:3 (2019), 175–188
|
| Просмотров: |
| Эта страница: | 215 | | Полный текст: | 61 | | Литература: | 25 | | Первая стр.: | 37 |
|
Пользовательское соглашение