In this paper we define a hierarchy, of length ω 2, 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.
A Hierarchy of LOOP Programs over Binary Trees / Fachini, Emanuela; M., Napoli. - In: INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS. - ISSN 0020-7160. - STAMPA. - 19:1(1986), pp. 3-22. [10.1080/00207168608803501]
A Hierarchy of LOOP Programs over Binary Trees.
FACHINI, Emanuela;
1986
Abstract
In this paper we define a hierarchy, of length ω 2, 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.