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

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

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



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






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


Модел. и анализ информ. систем, 2007, том 14, номер 2, страницы 12–16 (Mi mais128)  

О числе запретов, задающих периодическую последовательность

Г. Р. Челноков

Ярославский государственный университет

Аннотация: Рассматриваются последовательности $W$ периода $u$ над алфавитом из $l$ букв. Требуется однозначно определить последовательность $W$, указывая слова, не являющиеся ее подсловами. Для $n\in\mathbb N$ обозначим за $U_n$ множество слов $u$ длины $n$, не являющихся степенями (т.е. не представимых в виде $u=v^k$, $k>1$). Пусть $T(u^{\infty})$ — минимальное число запретов, задающих последовательность $u^{\infty}$. Обозначим
$$ m_n=\max_{u \in U_n} T(u^{\infty}),\quad r_n=\min_{u \in U_n} T(u^{\infty}). $$
Доказаны следующие теоремы:
Теорема 1. $m_n\le n(l-1)$.
Отметим, что оценка точна при бесконечно многих $n$ и реализуется, например, для периода, содержащего все слова некоторой фиксированной длины $t$ (т.е. $n=l^t$).
Теорема 2. $r_n\ge\log_2 n+1$.
Теорема 3. Существует возрастающая последовательность $n_i$, такая, что
$$ r_{n_i}\le\log_{\phi}n_i, \quadгде\quad \phi=\frac{1+\sqrt5}2. $$


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

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

УДК: 512.552.4+519.115.1
Поступила в редакцию: 29.04.2007

Образец цитирования: Г. Р. Челноков, “О числе запретов, задающих периодическую последовательность”, Модел. и анализ информ. систем, 14:2 (2007), 12–16

Цитирование в формате AMSBIB
\RBibitem{Che07}
\by Г.~Р.~Челноков
\paper О числе запретов, задающих периодическую последовательность
\jour Модел. и анализ информ. систем
\yr 2007
\vol 14
\issue 2
\pages 12--16
\mathnet{http://mi.mathnet.ru/mais128}
\elib{http://elibrary.ru/item.asp?id=13094512}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais128
  • http://mi.mathnet.ru/rus/mais/v14/i2/p12

    ОТПРАВИТЬ: 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
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:265
    Полный текст:57
    Литература:15

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019