PROOFS OF REFAL-5 FUNCTION BELONGING TO SOME SUBCLASSES OF FP-SPACE

Authors

  • Nikolay Kosovsky

Keywords:

Turing machine, polynomial number of steps, Refal-5, subclasses of the class FP-SPACE, subclasses of the class FP

Abstract

Complexity classes hierarchies for functions from both FP and FP-SPACE classes are introduced. Theorems about closure of these function classes of hierarchies as well as the classes of functions FP||LIN-SPACE and FP||QLIN-SPACE and classes of predicates P||LIN-SPACE and P||QLIN-SPACE under the definition of Refal-5 functions with bounded numbers of recursive calls and the used memory size are proved.

Downloads

Published

2013-06-30

Issue

No. 3 (2013)

Section

Computer science

License

Public offer

How to Cite

[1]
“PROOFS OF REFAL-5 FUNCTION BELONGING TO SOME SUBCLASSES OF FP-SPACE”, Comput. Tools Educ., no. 3, Jun. 2013, Accessed: Oct. 24, 2026. Available: http://cte.eltech.ru/ojs/index.php/kio/article/view/1345

Most read articles by the same author(s)