Hierarchies of primitive recursive wordsequence functions: Comparisons and decision problems (Q1073019)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Hierarchies of primitive recursive wordsequence functions: Comparisons and decision problems |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hierarchies of primitive recursive wordsequence functions: Comparisons and decision problems |
scientific article |
Statements
Hierarchies of primitive recursive wordsequence functions: Comparisons and decision problems (English)
0 references
1984
0 references
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.
0 references
LOOP programs on words
0 references
hierarchies of functions
0 references
hierarchies of programs
0 references
generalized hierarchies
0 references
storage hierarchies
0 references