Доказательства принадлежности рефал-5 функций некоторым подклассам FP-SPACE

Авторы

  • Н. К. Косовский

Ключевые слова:

машина Тьюринга, полиномиальное число шагов, рефал-5, подклассы класса FP-SPACE, подклассы класса FP

Аннотация

Вводятся иерархии классов сложности функций как из FP, так и из FP-SPACE. В статье доказывается теорема о замкнутости классов функций этих иерархий, а также классов функций FP||LIN-SPACE и FP||QLIN-SPACE и классов предикатов P||LIN-SPACE и P||QLIN-SPACE относительно определения рефал-5 функций с ограниченными сверху числом рекурсивных вызовов и величиной использованной памяти. С. 3-8.

Загрузки

Опубликован

30.06.2013

Выпуск

№ 3 (2013)

Раздел

Информатика

Лицензия

Авторский договор

Как цитировать

[1]
«Доказательства принадлежности рефал-5 функций некоторым подклассам FP-SPACE», Comput. Tools Educ., вып. 3, июн. 2013, просмотрено: окт. 24, 2026. доступно на: http://cte.eltech.ru/ojs/index.php/kio/article/view/1345

Наиболее читаемые статьи этого автора (авторов)