Войти / Регистрация
Корзина

  • Ваша корзина пуста
Войти / Регистрация
Корзина

  • Ваша корзина пуста

Статья «Об элементарных словарных функциях, получаемых на основе ограниченной префиксной конкатенации, "Дискретная математика"»

Авторы:
  • Марченков Сергей Серафимович1
стр. 44-55
Платно
1 Московский государственный университет имени М.В. Ломоносова
Ключевые слова:
  • операция ограниченной префиксной конкатенации
  • полиномиально вычислимая функция.
Аннотация:
На множестве словарных функций в алфавите вводится операция ограниченной префиксной конкатенации. На основе этой операций и операции суперпозиции определяется класс BPC полиномиально вычислимых функций. Устанавливается принадлежность классу BPC ряда словарных функций, а также замкнутость класса BPC относительно некоторых известных операций. Вводится некоторый тип двуленточных нестирающих машин Тьюринга и доказывается, что функции из класса BPC можно вычислить на машинах этого типа за полиномиальное время. Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 13-01-00958.

Архивные статьи (2015 год и ранее) доступны для ознакомления бесплатно, для скачивания их необходимо приобрести. Для просмотра материалов необходимо зарегистрироваться и авторизоваться на сайте.

Чтобы приобрести доступ к материалу для юридического лица, пожалуйста, свяжитесь с администрацией портала с помощью формы обратной связи либо по электронному адресу libnauka@naukaran.com.  

Действия с материалами доступны только авторизованным пользователям.