\growthfactor{w}>1\protect\)} % \end{figure*} % \apar{6-7} As every polynomial time bound can be exceeded by every exponential time bound, the following can be concluded\@. To denote classes of sets accepted in polynomial time bounds, we use the notation \(\polyfuncs\) for the set of all polynomials in a single variable~\(n\)\@. % \begin{alabsubtext}{Corollary}{2}{} % For every steady nonconstant position valuation \(s\), it holds that % \[\complexityclass{\(T\)-NSPACE-TIME}\left(n,\polyfuncs\right)\subseteq \classoflang{WGCSL}_{s}\] \sentence % \end{alabsubtext} % \apar{6-8}We therefore have all the relations depicted in Figure~6, where we concentrated on some specific classes because of clarity\@. % \begin{figure*} \fbox{\parbox[t]{\textwidth}{% \setlength{\unitlength}{0.175ex}% % \begin{picture}(355,560)(60,90) \put(250,631){\line(-6,-1){120}} \put(290,631){\line( 6,-1){120}} \put(130,612){\line( 0,-1){ 5}} \put(130,602){\makebox(0.4444,0.6667){.}} \put(130,598){\makebox(0.4444,0.6667){.}} \put(130,594){\makebox(0.4444,0.6667){.}} \put(130,575){\line( 0,-1){ 25}} \put(340,565){\line(-5, 1){85}} \put(340,555){\line(-6,-1){80}} \put(410,611){\line( 0,-1){ 5}} \put(410,602){\makebox(0.4444,0.6667){.}} \put(410,598){\makebox(0.4444,0.6667){.}} \put(410,594){\makebox(0.4444,0.6667){.}} \put(410,590){\line( 0,-1){ 25}} \put(410,550){\line( 0,-1){ 80}} \put(130,510){\line( 0,-1){ 20}} \put(130,470){\line( 0,-1){ 10}} \put(330,465){\line(-5, 1){ 60}} \put(340,410){\line(-6, 1){ 90}} \put(340,400){\line(-6,-1){ 80}} \put(410,450){\line( 0,-1){ 10}} \put(410,436){\makebox(0.4444,0.6667){.}} \put(410,432){\makebox(0.4444,0.6667){.}} \put(410,428){\makebox(0.4444,0.6667){.}} \put(410,425){\line( 0,-1){ 10}} \put(410,395){\line( 0,-1){ 95}} \put(345,295){\line(-5, 1){100}} \put(345,285){\line(-6,-1){ 95}} \put(410,280){\line( 0,-1){ 10}} \put(410,248){\line( 0,-1){ 12}} \put(410,215){\line( 0,-1){ 5}} \put(410,206){\makebox(0.4444,0.6667){.}} \put(410,202){\makebox(0.4444,0.6667){.}} \put(130,456){\makebox(0.4444,0.6667){.}} \put(130,452){\makebox(0.4444,0.6667){.}} \put(130,448){\makebox(0.4444,0.6667){.}} \put(130,445){\line( 0,-1){ 10}} \put(130,420){\line( 0,-1){ 25}} \put(130,355){\line( 0,-1){ 30}} \put(130,305){\line( 0,-1){ 25}} \put(410,198){\line( 0,-1){ 5}} \put(130,245){\line( 5,-4){145}} \put(295,110){\line( 0,-1){ 10}} \put(410,174){\line( 0,-1){ 5}} \put(410,164){\makebox(0.4444,0.6667){.}} \put(410,159){\makebox(0.4444,0.6667){.}} \put(410,154){\makebox(0.4444,0.6667){.}} \put(410,149){\line( 0,-1){ 5}} \put(410,144){\line(-5,-1){ 75}} \put(235,636){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ \(\classoflang{CSL}=\classoflang{WGCSL}_{s}\), \(s\) unsteady or zero points}}} \put( 70,580){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ \(\complexityclass{\(T\)-NSPACE-TIME} \left(n,\orderof{2^{k\mult n}}\right)\)}}} \put(340,555){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ \(\classoflang{WGCSL}_{2^{k}}=\classoflang{WGCSL}_{\frac{1}{2^{k}}}\) }}} \put( 70,535){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ \(\complexityclass{\(T\)-NSPACE-TIME} \left(n,\orderof{2^{q\mult k\mult n}}\right)\)}}} \put( 90,520){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ for \(\frac{k-1}{k}1\), and let \(s\) be a steady position valuation with \({\growthfactor{w}(s)=\growthfactor{w}}\)\@. The following statements are equivalent: % \begin{enumerate} \item[a)] \(\classoflang{WGCSL}_{\growthfactor{w}}=\classoflang{CSL}\)\@. % \item[b)] \(\classoflang{WGCSL}_{\growthfactor{w}}\) is closed under inverse homomorphism\@. % \item[c)] For every unsteady position valuation \(\tilde{s}\), for every grammar \(G\in\classofgrammar{WGCSG}_{\tilde{s}}\), there exists a grammar \(G'\in\classofgrammar{WGCSG}_{s}\) in Cremers normal form with \(\gramtolang(G')=\gramtolang(G)\)\@. % \item[d)] There exists an unsteady position valuation \(\tilde{s}\) satisfying the condition of c) above\@. % \end{enumerate} \sentence % Additionally, a) implies: % \begin{enumerate} % \item[e)] \(\complexityclass{\(T\)-NSPACE-TIME} \left(n,\orderof{\growthfactor{w}^{n}}\right)= \complexityclass{\(T\)-NSPACE}(n)\), % \end{enumerate} % and from this it can be concluded: % \begin{enumerate} % \item[f)] \(\classoflang{WGCSL}_{\growthfactor{v}}=\classoflang{CSL}\) for every \(\growthfactor{v}>\growthfactor{w}\)\@. % \end{enumerate} \sentence % \end{alabsubtext} % \asection{7}{Conclusion} % \apar{7-1} We have seen a characterization of \(\classoflang{CSL}\) by weakly growing context-sensitive grammars related to an unsteady position valuation (Section~4) and a characterization of the exponential time hierarchy of \(\classoflang{CSL}\) by classes of weakly growing context-sensitive languages related to steady position valuations (Section~6)\@. Equally interesting, we consider the question of whether the exponential time hierarchy for linear bounded automata collapses\@. % \apar{7-2} Theorem~10 proves that the following problems are equivalent: % \begin{itemize} % \item For every weakly growing context-sensitive grammar related to an unsteady position valuation \(\tilde{s}\), does there exist an equivalent grammar in a normal form of bounded order that is weakly growing context-sensitive related to a steady position valuation~\(s\)\@? % \item Is \(\classoflang{WGCSL}_{s}\) closed under inverse homomorphism for a steady position valuation~\(s\)\@? % \item Does the hierarchy of weakly growing context-sensitive language classes corresponding to different growth factors collapse down to a certain level\@? That is, do \(\classoflang{CSL}\) and \(\classoflang{WGCSL}_{s}\) coincide for a steady position valuation~\(s\)\@? % \item Does the exponential time hierarchy for \(\classoflang{CSL}\) collapse up to \(\classoflang{CSL}\)\@? That is, do \(\classoflang{CSL}\) and \(\complexityclass{\(T\)-NSPACE-TIME} \left(n,\orderof{\growthfactor{w}^{n}}\right)\) coincide for a certain \({\growthfactor{w}\in\universe{N}^{+}}\)\@? % \end{itemize} \sentence % If in the first question we allow an arbitrary position valuation instead of a steady one, we also must restrict ourselves to normal forms of order 2 (and thus end up with a steady position valuation again)\@. The reason lies in the fact that for each context-sensitive grammar there exists an equivalent grammar of order 3 that is in \(\classoflang{WGCSG}_{s}\), where \(s\) is an arbitrary unsteady position valuation with three valuated positions\@. This can be shown in the following way: % \begin{quote} % We restrict ourselves to the case \(s(1)