A generalized Grzegorczyk hierarchy and low complexity classes (Q1098838)

The author investigates initial classes of the generalized Grzegorczyk hierarchy of functions over words introduced by \textit{F. W. von Henke}, \textit{K. Indermark} and \textit{K. Weihrauch} [Automata, Languages and Programming, Proc. Symp. IRIA, Rocquencourt 1972, 549-561 (1973; Zbl 0357.02035)] which is an analogue of the Grzegorczyk hierarchy. Let us denote by \(\Sigma_ k\) an alphabet containing exactly k symbols. The author shows that for \(k\geq 2\) the class \({\mathcal E}^ 1(\Sigma_ k)\) is equal to the class of functions computable by algorithms, operating in polynomial time and linear space simultaneously and restricted to the arguments from \(\Sigma^*_ k\). The result is proved for a modification of Turing machines similar to those of \textit{A. P. Bel'tukov} [Zap. Nauchn. Semin. Leningr. Otd. Mat. Inst. Steklova 88, 30-46 (1979; Zbl 0429.03017)]. A series of other results concerning some classes of functions and relations belonging to initial classes are obtained.