Hierarchies of primitive recursive wordsequence functions: Comparisons and decision problems (Q1073019)

In this paper we consider wordsequence functions, i.e., functions of the type \(f:\Sigma^{*^ r}\to \Sigma^{*^ s}\) where \(\Sigma\) is a finite alphabet and \(r\geq 0\), \(s>0\). By starting with finite sets of basic functions and by taking the closure with respect to composition, cylindrification and iteration, we give some characterizations of primitive recursive wordsequence functions. We define some hierarchies of length \(\omega^ 2\) of these functions by bounding the number of successive compositions and the depth of the nested iterations in the definitions of the functions. In such a manner we obtain refinements of the Axt, Grzegorczyk and Meyer and Ritchie generalized hierarchies of length \(\omega\) of primitive recursive wordfunctions defined by \textit{F. W. von Henke}, \textit{K. Indermark} and \textit{K. Weihrauch} [Automata, Languages, Programming, Proc. Symp. Inst. Rech. Informatique Autom. (IRIA), Rocquencourt 1972, 549-561 (1973; Zbl 0357.02035)]. We consider LOOP programs on words [see \textit{G. Ausiello} and \textit{M. Moscarini}, Informatik Fachber. 5, 148-163 (1976; Zbl 0352.68035)] by allowing more than one output register, and we prove that the class of functions computed by these programs coincides with the class of primitive recursive wordsequence functions. The hierarchies of functions induce some hierarchies of programs. For the case of functions \(f:\Sigma^{*^ r}\to \Sigma^*\), our hierarchies are compared with the Axt et al. generalized hierarchies. We also compare our hierarchies with storage hierarchies, and we analyze the power of the LOOP programs as acceptors. Finally, we state some decidability results for the considered classes.