A recursive and a grammatical characterization of the exponential-time languages
B Monien - Theoretical Computer Science, 1976 - Elsevier
Theoretical Computer Science, 1976•Elsevier
We characterize the class of all languages which are acceptable in exponential time by
means of recursive and grammatical methods.(i) The class of all languages which are
acceptable in exponential time is uniquely characterized by the class of all (0-1)-functions
which can be generated, starting with the initial functions of the Grzegorczyk-class E 2, by
means of subtitution and limited recursion of the form f (x, y+ 1)= h (x, y), f (x, y), f (x, l (x, y))), l
(x, y)⩽ y.(ii) The class of all languages which are acceptable in exponential time is equal to …
means of recursive and grammatical methods.(i) The class of all languages which are
acceptable in exponential time is uniquely characterized by the class of all (0-1)-functions
which can be generated, starting with the initial functions of the Grzegorczyk-class E 2, by
means of subtitution and limited recursion of the form f (x, y+ 1)= h (x, y), f (x, y), f (x, l (x, y))), l
(x, y)⩽ y.(ii) The class of all languages which are acceptable in exponential time is equal to …
We characterize the class of all languages which are acceptable in exponential time by means of recursive and grammatical methods.(i) The class of all languages which are acceptable in exponential time is uniquely characterized by the class of all (0-1)-functions which can be generated, starting with the initial functions of the Grzegorczyk-class E 2, by means of subtitution and limited recursion of the form f (x, y+ 1)= h (x, y), f (x, y), f (x, l (x, y))), l (x, y)⩽ y.(ii) The class of all languages which are acceptable in exponential time is equal to the class of all languages generated by context-sensitive grammars with context-free control sets.
Elsevier