A generalized Grzegorczyk hierarchy and low complexity classes (Q1098838)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A generalized Grzegorczyk hierarchy and low complexity classes |
scientific article |
Statements
A generalized Grzegorczyk hierarchy and low complexity classes (English)
0 references
1987
0 references
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.
0 references
polynomial computability
0 references
generalized Grzegorczyk hierarchy of functions over words
0 references
Turing machines
0 references