|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Об элементарных словарных функциях, получаемых на основе ограниченной префиксной конкатенациистатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКДата последнего поиска статьи во внешних источниках: 18 марта 2016 г.
- Автор: Марченков С.С.
- Журнал: Дискретная математика
- Том: 27
- Номер: 3
- Год издания: 2015
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Первая страница: 44
- Последняя страница: 55
- DOI: 10.4213/dm1334
- Аннотация: На множестве словарных функций в алфавите {1,2} вводится операция ограниченной префиксной конкатенации. На основе этой операций и операции суперпозиции определяется класс BPC полиномиально вычислимых функций. Устанавливается принадлежность классу BPC ряда словарных функций, а также замкнутость класса BPC относительно некоторых известных операций. Вводится некоторый тип двуленточных нестирающих машин Тьюринга, вычисляющих функции за полиномиальное время, и доказывается, что функции из класса BPC можно вычислить на машинах этого типа.
- Добавил в систему: Марченков Сергей Серафимович