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

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

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


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




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

Дискретная математика, 2003, том 15, выпуск 2, страницы 52–62
DOI: https://doi.org/10.4213/dm193 (Mi dm193) 		 
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

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

С. С. Марченков
PDF полного текста (1280 kB) Список цитирования (4)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/dm193
Аннотация: Изучаются возвратные последовательности над конечными множествами и множеством $\mathbf N_0=\{0,1,2,\dots\}$. Сложность возвратных последовательностей над конечными множествами оценивается через сложность вычислений на детерминированных линейно ограниченных автоматах. Вводится понятие ветвящейся возвратной последовательности. Сложность ветвящихся возвратных последовательностей над конечными множествами оценивается через сложность вычислений на недетерминированных линейно ограниченных автоматах. Возвратными последовательностями над множеством $\mathbf N_0$ моделируются вычисления на многоленточных машинах Минского. Устанавливается неразрешимость некоторых проблем, относящихся к этому типу возвратных последовательностей.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 00–01–00351.
Статья поступила: 12.02.2002
Англоязычная версия:
Discrete Mathematics and Applications, 2003, Volume 13, Issue 2, Pages 167–178
DOI: https://doi.org/10.1515/156939203322109122
Реферативные базы данных:
УДК: 519.712
Образец цитирования: С. С. Марченков, “О сложности возвратных последовательностей”, Дискрет. матем., 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://mathscinet.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}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/dm193
  • https://doi.org/10.4213/dm193
  • https://www.mathnet.ru/rus/dm/v15/i2/p52
    • Эта публикация цитируется в следующих 4 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретная математика
    Статистика просмотров:
    Страница аннотации:523
    PDF полного текста:231
    Список литературы:50
    Первая страница:1
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024