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

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

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



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






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


Дискрет. матем., 2003, том 15, выпуск 2, страницы 52–62 (Mi dm193)  

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

О сложности возвратных последовательностей

С. С. Марченков


Аннотация: Изучаются возвратные последовательности над конечными множествами и множеством $\mathbf N_0=\{0,1,2,…\}$. Сложность возвратных последовательностей над конечными множествами оценивается через сложность вычислений на детерминированных линейно ограниченных автоматах. Вводится понятие ветвящейся возвратной последовательности. Сложность ветвящихся возвратных последовательностей над конечными множествами оценивается через сложность вычислений на недетерминированных линейно ограниченных автоматах. Возвратными последовательностями над множеством $\mathbf N_0$ моделируются вычисления на многоленточных машинах Минского. Устанавливается неразрешимость некоторых проблем, относящихся к этому типу возвратных последовательностей.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 00–01–00351.

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

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

Англоязычная версия:
Discrete Mathematics and Applications, 2003, 13:2, 167–178

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

УДК: 519.712
Статья поступила: 12.02.2002

Образец цитирования: С. С. Марченков, “О сложности возвратных последовательностей”, Дискрет. матем., 15:2 (2003), 52–62; Discrete Math. Appl., 13:2 (2003), 167–178

Цитирование в формате AMSBIB
\RBibitem{Mar03}
\by С.~С.~Марченков
\paper О сложности возвратных последовательностей
\jour Дискрет. матем.
\yr 2003
\vol 15
\issue 2
\pages 52--62
\mathnet{http://mi.mathnet.ru/dm193}
\crossref{https://doi.org/10.4213/dm193}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2006675}
\zmath{https://zbmath.org/?q=an:1051.03031}
\transl
\jour Discrete Math. Appl.
\yr 2003
\vol 13
\issue 2
\pages 167--178
\crossref{https://doi.org/10.1515/156939203322109122}


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

    ОТПРАВИТЬ: 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. С. С. Марченков, “О сложности полиномиальных возвратных последовательностей”, Пробл. передачи информ., 54:3 (2018), 67–72  mathnet; S. S. Marchenkov, “On the complexity of polynomial recurrence sequences”, Problems Inform. Transmission, 54:3 (2018), 258–262  crossref  isi
  • Дискретная математика
    Просмотров:
    Эта страница:340
    Полный текст:114
    Литература:28
    Первая стр.:1

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