A hierarchy of loop programs over binary trees

Abstract

In this paper we define a hierarchy, of length ω ², of LOOP programs over binary trees. Each class is obtained by considering the depth of nesting of a proper iteration over binary trees and the number of such iterations of maximum depth of nesting. In every class there is a function which bounds in dimension all the functions of the lower classes. We give a recursion theoretic characterization and investigate the properties of computation time closure for the classes of the hierarchy.

The hierarchy is compared with the hierarchy of functions over binary trees defined by Büning in [2] with respect to the set theoretical relationships. Moreover some decision problems for both the hierarchy are stated.

Keywords:

• Complexity hierarchy
• LOOP programs

C.R. Categories:

• F.1.3