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

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

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



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






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


Матем. заметки, 2012, том 92, выпуск 1, страницы 3–18 (Mi mz9483)  

О методе нахождения точных оценок длин выводов в системах Туэ

С. И. Адян

Математический институт им. В. А. Стеклова РАН

Аннотация: Рассматривается следующая система подстановок в алфавите из трех букв:
$$ \mathbf\Sigma=\langle a,b,c\mid a^2\to bc, b^2\to ac, c^2\to ab\rangle. $$
В работе изложено подробное доказательство результатов, которые были вкратце изложены в заметке автора [1]. Они давали ответ на поставленный в литературе конкретный вопрос о возможности нахождения полиномиальной верхней оценки длин выводов из данного слова в системе подстановок $\Sigma$. Вычислительной сложностью $\mathbf D(W)$ слова $W$ в системе подстановок $\Sigma$ называется максимально возможная длина цепочки подстановок, начинающейся со слова $W$. Через $\mathbf D(l)$ обозначается максимальное значение этой функции на всех словах длины $l$. Доказано, что максимальная вычислительная сложность $\mathbf D(W)$ для слов данной длины $|W|=m+2$ достигается только для слов вида $W=c^2b^m$ и $W=b^ma^2$. Для вычислительной сложности этих слов получена следующая точная оценка:
$$ \mathbf D(m+2)=\mathbf D(c^2b^m)=\mathbf D(b^ma^2) =\rceil\frac{3m^2}{2}\lceil+m+1<\frac{3(m+1)^2}{2}, $$
где для данных целых чисел $x$ и $y$ через $\rceil x/y\lceil$ обозначается результат округления дроби $x/y$ до ближайшего сверху целого числа.
Библиография: 5 названий.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований
Министерство образования и науки Российской Федерации
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований и программы “Ведущие научные школы”.


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

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

Англоязычная версия:
Mathematical Notes, 2012, 92:1, 3–15

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

Тип публикации: Статья
УДК: 510.52+512.54.05
Поступило: 09.01.2012

Образец цитирования: С. И. Адян, “О методе нахождения точных оценок длин выводов в системах Туэ”, Матем. заметки, 92:1 (2012), 3–18; Math. Notes, 92:1 (2012), 3–15

Цитирование в формате AMSBIB
\RBibitem{Adi12}
\by С.~И.~Адян
\paper О методе нахождения точных оценок длин выводов в~системах Туэ
\jour Матем. заметки
\yr 2012
\vol 92
\issue 1
\pages 3--18
\mathnet{http://mi.mathnet.ru/mz9483}
\crossref{https://doi.org/10.4213/mzm9483}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3201536}
\zmath{https://zbmath.org/?q=an:06138356}
\elib{http://elibrary.ru/item.asp?id=20731563}
\transl
\jour Math. Notes
\yr 2012
\vol 92
\issue 1
\pages 3--15
\crossref{https://doi.org/10.1134/S0001434612070012}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000308042500001}
\elib{http://elibrary.ru/item.asp?id=20473314}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84865706169}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mz9483
  • https://doi.org/10.4213/mzm9483
  • http://mi.mathnet.ru/rus/mz/v92/i1/p3

    ОТПРАВИТЬ: 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
  • Математические заметки Mathematical Notes
    Просмотров:
    Эта страница:534
    Полный текст:66
    Литература:34
    Первая стр.:21

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