% The Chicago Journal of Theoretical Computer Science, Volume 1996, Article 4
% Published by MIT Press, Cambridge, Massachusetts USA
% Copyright 1996 by Massachusetts Institute of Technology
%
\newtoks\rstyle
\rstyle={cjlook}
%
\ifx\documentclass\undeftex
\documentstyle[v1.1,published]{cjstruct}
\else
\documentclass[v1.1,published]{cjstruct}
\fi
%
% Local resources for this article.
%
\usestyleresource{amstex}
\catcode`\@=12
%
% Local macro definitions for this article.
%
\catcode`\@=11
\ifx\nopagebreakbeginpar\undeftex
  \newcommand{\nopagebreakbeginpar}{\@beginparpenalty10000}
\fi
\ifx\nopagebreakendpar\undeftex
  \newcommand{\nopagebreakendpar}{\@endparpenalty10000}
\fi
\catcode`\@=12
%
\ifx\providecyrillic\undeftex
  \newcommand{\providecyrillic}{%
    \input cyracc.def
    \font\tencyr=wncyr10 % scaled 1200
    \def\cyr{\tencyr\cyracc}
}
%
\ifltwoe\else\newcommand{\emph}[1]{{\em #1\/}}\fi
\ifltwoe\else\newcommand{\textit}[1]{{\it #1\/}}\fi
\ifltwoe\else\newcommand{\textup}[1]{{\rm #1\/}}\fi
\ifltwoe\else\newcommand{\textsl}[1]{{\sl #1\/}}\fi
\ifltwoe\else\newcommand{\mathcal}[1]{{\cal #1\/}}\fi
%
\newcommand\nohyphenl[1]{{\discretionary{}{}{}{#1}}}
%
\newcommand{\asteqnmark}{$\ast$}
\newcommand{\primerulemark}{${}^{\prime}$}
%
\newcommand{\assigned}{\mathrel{:=}}
%
\newcommand{\identfunc}{\text{id}}
\mathstyleclass{\flanguage}{\mathord}{\textsl}
\mathstyleclass{\classoflang}{\mathord}{\textsl}
\mathstyleclass{\classofclassoflang}{\mathord}{\textup}
\mathstyleclass{\classofgrammar}{\mathord}{\textsl}
\mathstyleclass{\complexityclass}{\mathord}{\textsl}
%
\newcommand{\equdef}{\mathrel{\overset{\scriptscriptstyle\text{def}}=}}
\newcommand{\propsub}{%
  \mathchoice%
    {\mathbin{\overset{\raisebox{0.25ex}{\(\textstyle\cdot\)}}{\smash{-}}}}%
    {\mathbin{\overset{\raisebox{0.25ex}{\(\textstyle\cdot\)}}{\smash{-}}}}%
    {\mathbin{\overset{\scriptscriptstyle\raisebox{0.1ex}{\(\scriptstyle\cdot\)}}{\smash{-}}}}%
    {\mathbin{\overset{\scriptscriptstyle\raisebox{0.1ex}{\(\scriptstyle\cdot\)}}{\smash{-}}}}%
}
\newcommand{\gramtolang}{L}
\newcommand{\universe}[1]{\Bbb{#1}}
\newcommand{\setof}[2]{\left\{\,#1:#2\,\right\}}
\newcommand{\setunion}{\cup}
\newcommand{\setintsct}{\cap}
\newcommand{\sunionofset}[2]{\bigcup_{#1}#2}
\newcommand{\funcspace}[2]{#1\mathbin{\rightarrow}#2}
\newcommand{\oftype}{\colon}
\newcommand{\strlength}[1]{\mathopen{|}#1\mathclose{|}}
\newcommand{\emptystring}{\varepsilon}
\newcommand{\concatenate}{\cdot}
\newcommand{\catlang}{\cdot}
\newcommand{\derives}[1]{\mathrel{\underset{#1}{\Longrightarrow}}}
\newcommand{\multiderives}[1]{\mathrel{\overset{*}{\derives{#1}}}}
\newcommand{\restrfun}[2]{#1\mathord{|}_{#2}}
\newcommand{\mult}{\cdot}
\newcommand{\gramord}{\operatorname{ord}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\absvalue}[1]{\mathopen{|}#1\mathclose{|}}
\newcommand{\tapetriple}[3]{\!\left[\begin{array}{@{}c@{}}#1\\#2\\#3\end{array}\right]\!\!}
\newcommand{\tapepair}[2]{\!\left[\begin{array}{@{}c@{}}#1\\#2\end{array}\right]\!\!}
\newcommand{\longvdash}{\mathrel{\smash{\mapstochar\mathrel{-\!\!-}}\vphantom{\longmapsto}}}
\newcommand{\compsteps}[1]{\mathrel{\overset{*}{\underset{#1}{\longvdash}}}}
\newcommand{\omittapeentry}{\;}
\newcommand{\leftendtape}{\heartsuit}
\newcommand{\rightendtape}{\diamondsuit}
\newcommand{\tapereversemark}{\star}
\catcode`\@=13
\newcommand{\extendarrow}[1]{\mathrel{@>>{#1}>}}
\catcode`\@=12
\newcommand{\swallower}[1]{\mathcal{#1}}
\newcommand{\condval}[1]{\left\{\begin{array}{ll}#1\end{array}\right.}
\newcommand{\orderof}[1]{O(#1)}
\newcommand{\setsize}[1]{\mathopen{|}#1\mathclose{|}}
\newcommand{\counter}[1]{\mathcal{#1}}
\newcommand{\ceiling}[1]{\left\lceil#1\right\rceil}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\polyfuncs}{\text{\textup{pol}}}
%
\newcommand{\growthfactor}[1]{\mathrm{#1}}
\newcommand{\rulename}[1]{\text{\textup{#1}}}
%
\providecyrillic
%
\newcommand{\prooffontshape}{\fontshape{n}\selectfont}
\newcommand{\exampfontshape}{\fontshape{n}\selectfont}
\newcommand{\remarkfontshape}{\fontshape{n}\selectfont}
%
% Macros for the publisher's comment
%
% The circle R symbol for a registered trade name is adapted from the
% circled c copyright symbol defined in The TeXBook by Donald Knuth.
%
\def\registered{\({}^{\ooalign%
    {\hfil\raise.07ex\hbox{{\tiny\textup{R}}}%
    \hfil\crcr\scriptsize\mathhexbox20D\cr}}\)}
%
% Macros for the editors' comment
%
% The cross symbol indicates a recently deceased editor.
%
\ifx\deceased\undeftex
  \newcommand{\deceased}[1]{\dag#1}
\fi
%
% end of local macro definitions for this article
%
\begin{document}
%
\begin{articleinfo}
%
\publisher{The MIT Press}
%
\publishercomment{%
  {\Large
    \begin{center}
      Volume 1996, Article 4\\
      \textit{13 November 1996}
    \end{center}
  }
  \par\noindent
  ISSN 1073--0486\@. MIT Press Journals, 55 Hayward St., Cambridge, MA
  02142 USA; (617)253-2889;
  \emph{journals-orders@mit.edu, journals-info@mit.edu}\@.
  Published one article at a time in \LaTeX\ source form on the
  Internet\@. Pagination varies from copy to copy\@. For more
  information and other articles see:
  \begin{itemize}
    \item \emph{http://www-mitpress.mit.edu/jrnls-catalog/chicago.html}
    \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/}
    \item \emph{gopher.mit.edu}
    \item \emph{gopher.cs.uchicago.edu}
    \item anonymous \emph{ftp} at \emph{mitpress.mit.edu}
    \item anonymous \emph{ftp} at \emph{cs.uchicago.edu}
  \end{itemize}
  \sentence
  \par\noindent
  The \emph{Chicago Journal of Theoretical Computer Science} is
  abstracted or indexed in \emph{Research Alert,\registered
  SciSearch,\registered Current Contents\registered/Engineering
  Computing \& Technology}, and \emph{CompuMath Citation Index\@.\registered}
}
%
\copyrightstmt{%
  \copyright 1996 The Massachusetts Institute of Technology\@.
  Subscribers are licensed to use journal articles in a variety of
  ways, limited only as required to insure fair attribution to authors
  and the journal, and to prohibit use in a competing commercial
  product\@. See the journal's World Wide Web site for further
  details\@. Address inquiries to the Subsidiary Rights Manager, MIT
  Press Journals; (617)253-2864;
  \emph{journals-rights@mit.edu}\@.\pagebreak[2]
}
%
\journal{Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science}
%
\journalcomment{%
  The \emph{Chicago Journal of Theoretical Computer Science}
  is a peer-reviewed scholarly
  journal in theoretical computer science\@. The journal is committed
  to providing a forum for significant results on theoretical
  aspects of all topics in computer science\@.
  \par
  \begin{trivlist}
    \item[\emph{Editor in chief:}] Janos Simon
    \item[\emph{Consulting editors:}]
      Joseph Halpern, Stuart A.\ Kurtz, Raimund Seidel
    \item[\emph{Editors:}]
      \begin{tabular}[t]{lll}
        Martin Abadi & Greg Frederickson & John Mitchell \\
        Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\
        Eric Allender & Georg Gottlob & Gil Neiger \\
        Tetsuo Asano & Vassos Hadzilacos & David Peleg \\
        Laszl\'o Babai & Juris Hartmanis & Andrew Pitts \\
        Eric Bach & Maurice Herlihy & James Royer \\
        Stephen Brookes & Stephen Homer & Alan Selman \\
        Jin-Yi Cai & Neil Immerman & Nir Shavit \\
        Anne Condon & \deceased{Paris Kanellakis} & Eva Tardos \\
        Cynthia Dwork & Howard Karloff & Sam Toueg \\ 
        David Eppstein & Philip Klein & Moshe Vardi \\
        Ronald Fagin & Phokion Kolaitis & Jennifer Welch \\
        Lance Fortnow & Stephen Mahaney & Pierre Wolper \\
        Steven Fortune & Michael Merritt
      \end{tabular}
    \vspace{1ex}
    \item[\emph{Managing editor:}] Michael J.\ O'Donnell
    \vspace{1ex}
    \item[\emph{Electronic mail:}] \emph{chicago-journal@cs.uchicago.edu}
  \end{trivlist}
\sentence
}
%
\bannerfile{cjtcs-banner.tex}
%
\volume{1996}
%
\articleid{4}
%
\selfcitation{
     @article{cj96-04,
       author={Gerhard Buntrock and Gundula Niemann},
       title={Weakly Growing Context-Sensitive Grammars},
       journal={Chicago Journal of Theoretical Computer Science},
       volume={1996},
       number={4},
       publisher={MIT Press},
       month={November},
       year={1996}
     }
}
%
\begin{retrievalinfo}
\end{retrievalinfo}
%
\title{Weakly Growing Context-Sensitive Grammars}
\shorttitle{Weakly Growing CSGs}
\collectiontitle{}
%
\begin{authorinfo}
%
% Correction to error in cjstruct.sty version 1.1.
%
\def\fixversion{1.1}
\ifx\cjversion\fixversion
  \renewcommand{\printname}[1]{
    \global\authorstring={#1}
    \global\authorstrue
    \ifinfo\item Printed name: #1\fi
  }
\fi
%
% End of correction.
%
   \printname{Gerhard Buntrock}
   \collname{}{Buntrock, Gerhard}
   \begin{institutioninfo}
       \instname{Medizinische Universit\"at zu L\"ubeck}
       \department{Institut f\"ur Theoretische Informatik}
       \address{Wallstr.\ 40}{L\"ubeck}{}{Germany}{D-23560}
   \end{institutioninfo}
   \email{buntrock@informatik.mu-luebeck.de}
\end{authorinfo}
%
\begin{authorinfo}
%
   \printname{Gundula Niemann}
   \collname{}{Niemann, Gundula}
   \begin{institutioninfo}
       \instname{Universit\"at W\"urzburg}
       \department{Institut f\"ur Informatik}
       \address{Am Exerzierplatz 3}{W\"urzburg}{}{Germany}{D-97072}
   \end{institutioninfo}
   \email{niemann@informatik.uni-wuerzburg.de}
\end{authorinfo}
%
\shortauthors{Buntrock and Niemann}
%
\support{%
  Gerhard Buntrock's work was partly supported by a grant from the DFG
  (DFG-Projekt Wa 847/1-1)\@.%
}
%
\begin{editinfo}
  \submitted{8}{9}{1995}\reported{29}{2}{1996}
  \submitted{28}{5}{1996}\reported{6}{8}{1996}\published{13}{11}{1996}
\end{editinfo}
\end{articleinfo}
%
\begin{articletext}
% 
\begin{abstract}
%
\apar{Abstract-1}
This paper introduces \emph{weakly growing context-sensitive
grammars}\@. Such grammars generalize the class of growing
context-sensitive grammars (studied by several authors), in that these
grammars have rules that ``grow'' according to a position valuation\@.
%
\apar{Abstract-2}
If a position valuation coincides with the initial part of an
exponential function, it is called a \emph{steady} position
valuation\@. All others are called \emph{unsteady}\@. The complexity
of the language generated by a grammar depends crucially on whether
the position valuation is steady or not\@. More precisely, for every
unsteady position valuation, the class of languages generated by
\(\classofgrammar{WGCSG}\)s with this valuation coincides with the
class \(\classoflang{CSL}\) of context-sensitive languages\@. On the
other hand, for every steady position valuation, the class of languages
generated corresponds to a level of the hierarchy of exponential
time-bounded languages in \(\classoflang{CSL}\)\@. We show that the
following three conditions are \nohyphenl{equivalent}:
%
\begin{itemize}
%
\item The hierarchy of exponential time-bounded languages in
\(\classoflang{CSL}\) collapses\@.
%
\item There exists a class defined by an unsteady position valuation
such that there is also a normal form of order 2 (e.g., Cremers or
Kuroda normal form) for that class\@.
%
\item There exists a class defined by a steady position valuation that
is closed under inverse homomorphisms\@.
%
\end{itemize}
%
\end{abstract}
%
Some of these results were presented at LATIN'95 at Valpara\'iso, Chile\@.
%
\asection{1}{Introduction}
%
\apar{1-1}
A beautiful theory always has simple concepts and remarkable
results\@. Here we investigate a widely unknown but nice part of the
class of context-sensitive languages (\(\classoflang{CSL}\))\@.
%
\apar{1-2}
Our simple concept consists of a valuation of strings, and
concentration on the context-sensitive grammars that are growing under
such a valuation\@. As a result, we get characterizations of known
double-bounded complexity classes by this quite different concept\@.
Namely, we view the exponential time-bounded languages in
\(\classoflang{CSL}\), where \(\classoflang{CSL}\) is the class of
languages that can be recognized by a Turing machine in linear
space\@. Little is known about such dual-bounded classes; see, e.g.,
\cite{cj96-04-11}, \cite{cj96-04-24}, \cite{cj96-04-03}, and
\cite{cj96-04-25}\@. Wolfgang Paul asks in general which kind of speedup
theorem holds for space-bounded computations (see
\cite{cj96-04-23})\@. We concentrate on this question for the case of
linear-bounded automata\@. It is shown that this problem can be
reformulated using our concept, which comes from formal language
theory: We ask whether a particular class of languages is
characterized by a class of normal form grammars of order 2 (i.e.,
left and right sides of rules have length at most 2), or,
equivalently, whether another class is closed under inverse
homomorphism\@.
%
\apar{1-3}
Noam Chomsky has already observed in his famous work that
\(\classoflang{CSL}\) is characterized by monotone grammars, that is,
grammars in which in every rule a string is replaced by a string that
is at least as long as the first one \cite{cj96-04-10}\@. We will use
this characterization as a definition\@.
%
\apar{1-4}
By replacing ``at least as long as'' in the definition of the class
\(\classofgrammar{CSG}\) of context-sensitive grammars by ``longer
than,'' we obtain growing context-sensitive grammars
(\(\classofgrammar{GCSG}\)) which define the class of growing
context-sensitive languages (\(\classoflang{GCSL}\))\@. Elias Dahlhaus
and Manfred Warmuth investigated the complexity of
\(\classoflang{GCSL}\) and found out that \(\classoflang{GCSL}\) is
contained in \(\classoflang{LOGCFL}\) \cite{cj96-04-13}, the class of
such languages that can be transformed into a context-free language
(\(\classoflang{CFL}\)) using logarithmic space (\cite{cj96-04-30},
\cite{cj96-04-26})\@. Note that \(\classoflang{LOGCFL}\) is a subclass
of the class \(\complexityclass{P}\) of languages recognizable
deterministically in polynomial time\@. If we valuate the symbols of a
\(\classofgrammar{CSG}\) with a homomorphic mapping into the natural
numbers with addition, and demand that in every rule the sum of the
values of the symbols increases, this type of grammar
(quasi-\(\classofgrammar{GCSG}\), or \(\classofgrammar{QGCSG}\) for
short) characterizes \(\classoflang{GCSL}\) (\cite{cj96-04-07},
\cite{cj96-04-08}, \cite{cj96-04-06})\@. Unfortunately, the class
\(\classoflang{GCSL}\) is very weak\@.
\ifx\customadjusta\undeftex\else\customadjusta\fi
Not even the language
\(\flanguage{COPY}\equdef\setof{ww}{w\in\{a,b\}^*}\) is contained in
\(\classoflang{GCSL}\) (\cite{cj96-04-05}, see also~\cite{cj96-04-09})\@.
%
\apar{1-5}
Weakly growing context-sensitive grammars (\(\classofgrammar{WGCSG}\))
are a generalization of \(\classofgrammar{QGCSG}\)\@. In a
\(\classofgrammar{WGCSG}\) we valuate the positions as well as the
symbols inside a rule: Every position inside a rule is related to a
certain value\@. The valuation of a side of a rule is obtained by the
sum of the products of the symbol valuation and the position valuation
for every symbol\@. A context-sensitive grammar is called weakly
growing context-sensitive related to a certain position valuation
(\(\classofgrammar{WGCSG}_{s}\), where \(s\) stands for the position
valuation), if there exists a symbol valuation such that for every
rule the valuation of the left-hand side is lower than that of the
right-hand side\@. (This is defined precisely in Definition~2\@.) The
weakly growing context-sensitive languages related to constant
position valuations characterize \(\classoflang{GCSL}\)\@. We will
show that this definition is robust under some natural changes\@.
%
\apar{1-6}
The valuation of positions gives the possibility to interchange two
symbols by a rule\@. This can be used to prove \(\flanguage{COPY}\in
\classoflang{WGCSL}_{s}\) for every nonconstant position valuation
\(s\)\@. On the other hand, it can easily be seen that it is not
possible to interchange two symbols back and forth in the same
grammar\@. Thus we know that \(\classofgrammar{WGCSG}_{s}\) is
strictly contained in \(\classofgrammar{CSG}\) for each position
valuation \(s\)\@. The question as to whether or not the corresponding
language classes are strictly contained in \(\classoflang{CSL}\) will
be viewed later\@.
%
\apar{1-7}
For important language classes we expect some essential closure
properties\@. Clearly, the closure under non-\(\emptystring\)-free
homomorphisms of \(\classoflang{WGCSL}_{s}\) yields the class of all
recursively enumerable sets; i.e., \(\classoflang{WGCSL}_{s}\) is a
basis for recursively enumerable sets (the notion of a basis was
originally introduced by Raymond Smullyan in
\cite{cj96-04-29})\@. With standard arguments the following can be
proved: For every position valuation \(s\), the class
\(\classoflang{WGCSL}_{s}\) is closed under
\(\emptystring\)-free homomorphism, union, \(\emptystring\)-free
regular substitution, concatenation, and intersection with regular
sets\@. Additionally it can be shown that \(\classoflang{WGCSL}_{s}\)
is closed under transposition for every position valuation~\(s\)\@.
%
\apar{1-8}
What is missing, e.g., for \(\classoflang{WGCSL}_{s}\) to be an
abstract family of languages (or \(\classofclassoflang{AFL}\), see any
good introduction to formal language theory, such as \cite{cj96-04-27}
or \cite{cj96-04-16}), is the closure under inverse homomorphism and
also under \mbox{\(k\)-bounded} homomorphism\@. Here from
\cite{cj96-04-14} it is known that if the one holds, then so does the
other and vice versa, because of the closure properties we already
know\@. The closure under inverse homomorphism here can neither be
proved nor disproved in general; a main result in this context is the
equivalence of this problem to the problem of whether all linear
space-bounded automata can be simulated by linear space-bounded
automata with an additional universal exponential time bound\@. The
reason for this equivalence lies in the fact that for each nonconstant
position valuation, the closure under inverse homomorphism of
\(\classoflang{WGCSL}_{s}\) equals \(\classoflang{CSL}\)\@.
%
\apar{1-9}
To prove these results we distinguish \emph{steady} and
\emph{unsteady} position valuations: A position valuation is steady if
it coincides with the initial part of an exponential function\@. We
refer to the base of that corresponding function as the growth factor
of the position valuation\@. In the other case, the position valuation
is unsteady\@.
%
\apar{1-10}
It turns out that steady position valuations are uniquely extendible
to infinite position valuations such that all strings can be
valuated\@. Moreover, the number of derivation steps can be bounded
by the valuation of the derived string\@. This gives the result that
for a steady position valuation every weakly growing context-sensitive
grammar related to it can produce only sets acceptable by linear
space-bounded automata in a certain exponential time, where the base
of the bounding exponential function is the growth factor of the
position valuation (if it is monotone increasing)\@. To get this
result so tight, we transfer Gladkii's Connectivity Theorem (see
\cite{cj96-04-15}) to \(\classoflang{WGCSL}\)s\@. On the other hand,
for every language that can be recognized by a linear space-bounded
automaton there exists a steady position valuation \(s\) such that
this language belongs to \(\classoflang{WGCSL}_{s}\)\@. To get a very
tight relation here, we introduce a new type of counters: grammars
that count\@.
%
\apar{1-11}
Furthermore, the weakly growing context-sensitive language classes
corresponding to different growth factors build up a linearly
inclusion-ordered hierarchy that characterizes the exponential time
hierarchy for \(\classoflang{CSL}\) in terms of necessary and
sufficient conditions for the hierarchy to collapse\@.
%
\apar{1-12}
For unsteady position valuations, there does not exist an infinite
extension such that the value of a sentential form increases if and
only if a weakly growing context-sensitive rule is applied\@. To the
contrary: We present a collection of rules which when applied to a
given sentential form lead to a decrement of the value of that
sentential form\@. By this we will show that arbitrarily long
derivations are possible\@. We interpret this to be the reason that
for every unsteady position valuation the corresponding class of
weakly growing context-sensitive grammars characterizes
\(\classoflang{CSL}\)\@.
%
\apar{1-13}
Another important difference between the steady and unsteady cases
consists in the existence of normal forms of order 2\@. Note that
every \(s\)-weakly growing context-sensitive grammar in a normal form
of order 2 is one related to a steady position valuation\@. Here we
know that for every steady position valuation \(s\) and every weakly
growing context-sensitive grammar related to it there exists an
equivalent \(\classofgrammar{WGCSG}\) of the same type in normal
form\@. This can be proved using an obvious transformation\@. For this
we will use Cremers normal form, which has the advantage of having a
minimal number of different types of rules\@. Additionally, it turns
out that the growth factor of a steady position valuation
characterizes a weakly growing context-sensitive language class and
that the language classes corresponding to a growth factor and its
reciprocal value coincide\@. For unsteady position valuations, the
obvious transformation to reduce the order of a rule, and similar
transformations, do not work\@. Thus we obtain the equivalence of the
following problems\@.
%
\begin{itemize}
%
\item Does the exponential time hierarchy for \(\classoflang{CSL}\)
collapse\@? That is, can all linear space-bounded automata be
simulated by linear space-bounded automata with an additional
universal exponential time bound\@?
%
\item Does there exist a steady position valuation such that the 
corresponding class of weakly growing context-sensitive languages 
coincides with \(\classoflang{CSL}\)\@?
%
\item Does there exist a steady position valuation such that the 
corresponding class of weakly growing context-sensitive languages is 
closed under inverse homomorphism\@?
%
\item Does there exist an unsteady position valuation such that the 
following holds: Every weakly growing context-sensitive grammar
related to this position valuation can be transformed into an
equivalent grammar in a normal form of order 2 that is weakly growing
context-sensitive related to some position valuation\@?
%
\end{itemize}
%
\asection{2}{Preliminaries}
%
\apar{2-1}
We will denote the set of positive and negative integers by
\(\universe{Z}\), the set of natural numbers by \(\universe{N}\), the
set \(\universe{N}\setminus\{0\}\) by \(\universe{N}^{+}\), the set of
rational numbers by \(\universe{Q}\), and the set of positive rational
numbers by \(\universe{Q}^{+}\)\@. Denote modified subtraction
by~\(\propsub\)\@.
%
\apar{2-2}
We will denote a linear-bounded automaton by
\(M=(\Sigma,Q,\Gamma,q_{0},\delta,F)\), where
\(\Sigma\subseteq\Gamma\) is the input alphabet, \(Q\) is the set of
states, \(\Gamma\) is the working alphabet, \(q_{0}\) is the start state,
\(\delta\oftype\funcspace{(Q\times\Gamma)}{(Q\times\Gamma\times\{L,R\})}\)
is the transition function, and \(F\) is the set of accepting
states\@. By \(uqv\) we denote a configuration of \(M\), where \(uv\)
is the content of the working tape, \(q\) is the actual state, and the
first symbol of \(v\) is being read\@. By \(K_{1}\compsteps{M}K_{2}\)
we denote that configuration \(K_{2}\) is reachable from configuration
\(K_{1}\) by a computation of \(M\) (see, e.g., \cite{cj96-04-17} for
a detailed definition)\@. The subscript \(M\) is sometimes omitted when
it is obvious from the context\@. By \(M=(\Sigma,Q,q_{0},\delta,F)\) we
denote a finite automaton, where the signature of \(\delta\) is
appropriately changed\@. Additionally, we use
\(\delta^{*}\oftype\funcspace{Q\times\Sigma^{*}}{Q}\) to denote the
extension of \(\delta\) to \(Q\times\Sigma^{*}\)\@.
%
\apar{2-3}
A \emph{context-sensitive grammar} (\(\classofgrammar{CSG}\)) is a
quadruple \(G=\langle N,T,S,P\rangle\), where \(N\) and \(T\) are
finite disjoint alphabets of nonterminal and terminal symbols,
respectively, \(S\in N\) is the start symbol, and \(P\) is a finite
set of rules (productions) of the form \(\alpha\to\beta\) with
\(\alpha,\beta\in(N\setunion T)^{*}\), where \(\alpha\) contains at
least one nonterminal symbol, and
\(\strlength{\alpha}\leq\strlength{\beta}\) or
\((\alpha\to\beta)=(S\to\emptystring)\), and if
\((S\to\emptystring)\in P\), \(S\) does not appear on the right-hand
side of any rule\@. The corresponding language class is denoted by
\(\classoflang{CSL}\)\@.
%
\apar{2-4}
If \(u,v\in(N\setunion T)^{*}\) are sentential forms, we say \(u\)
\emph{derives} \(v\) \emph{in} \(G=\langle N,T,S,P\rangle\), denoted
by \(u\derives{} v\), if there exist
\(x,y,\alpha,\beta\in(N\setunion T)^{*}\) such that
\(u=x\alpha y,v=x\beta y\), and \((\alpha\to\beta)\in P\)\@. Let
\(\multiderives{}\) denote the reflexive and transitive closure of
\(\derives{}\)\@. Thus the \emph{language} \(\gramtolang(G)\)
generated by a grammar \(G\) is described by
\(\gramtolang(G)\equdef\setof{w\in T^{*}}{S\multiderives{G}w}\)\@.
For a language \(L\subseteq\Sigma^{*}\), the transposition \(L^{T}\)
of \(L\) is defined by
\(L^{T}\equdef\setof{w}{w^{T}\in L}\), where \(w^{T}\) denotes the
transposition of the string \(w\in\Sigma^{*}\) inductively defined as
follows: Define \(\emptystring^{T}\equdef\emptystring\), and for each
\(v\in\Sigma^{*}\) and each \(a\in\Sigma\) define \((av)^{T}\) to be
\(v^{T}a\)\@. Similarly,
\(L_{1}\catlang L_{2}\equdef\setof{w\concatenate v}%
{w\in L_{1}\text{, }v\in L_{2}}\), where \(w\concatenate v=wv\) is
\(w\) concatenated with~\(v\)\@.
%
\apar{2-5}
Grammars with \(\alpha\in N\) for each rule \((\alpha\to\beta)\in P\)
are called \emph{context-free}\@. The corresponding language class is
denoted by \(\classoflang{CFL}\)\@. Grammars with \(\alpha \in N\) and
\(\beta\in N\catlang T\setunion T\) for each rule
\((\alpha\to\beta)\in P\setminus\{(S\to\emptystring)\}\) are called
\emph{regular}\@. The corresponding language class is denoted by
\(\classoflang{REG}\)\@.
%
\apar{2-6}
By replacing the inequality in the definition of context-sensitive
grammars by a strict inequality, we obtain growing context-sensitive
grammars (\(\classofgrammar{GCSG}\)) that generate the growing
context-sensitive languages (\(\classoflang{GCSL}\)) (see
\cite{cj96-04-13}, also \cite{cj96-04-07}, \cite{cj96-04-20})\@.
The class \(\classoflang{GCSL}\) is placed properly between
\(\classoflang{CFL}\) and \(\classoflang{CSL}\) (\cite{cj96-04-13},
also see~\cite{cj96-04-20})\@.
%
\apar{2-7}
Instead of just counting the symbols appearing in a rule (as we did
above), we can assign each symbol a certain value (or weight)\@. A
grammar \(G=\langle N,T,S,P\rangle\) is called \emph{quasi-growing
context-sensitive}
\ifx\customadjustb\undeftex\else\customadjustb\fi
if it is context-sensitive and there exists a function
\(f\oftype\funcspace{N\setunion T}{\universe{N}}\) such that for each
rule
\((\alpha_{1}\dots\alpha_{n}\to\beta_{1}\dots\beta_{m})\in P\):
%
\[\sum_{i=1}^{n}f(\alpha_{i})<\sum_{i=1}^{m}f(\beta_{i}) 
\text{ or }(\alpha\to\beta)=(S\to\emptystring)\]
\sentence
%
The corresponding set of grammars is denoted by
\(\classofgrammar{QGCSG}\)\@. The function \(f\) is called a
\emph{symbol valuation for} \(G\)\@. By \(\restrfun{f}{N}\) we denote
the restriction of \(f\) to the set~\(N\)\@.
%
\apar{2-8}
If in the definition of \(\classofgrammar{QGCSG}\) we omit the
requirement of context-sensitivity, but keep the requirement that if
\((S\to\emptystring)\in P\), \(S\) does not appear on the right-hand
side of any rule, we obtain the \emph{quasi-growing grammars}\@.
%
\apar{2-9}
In \cite{cj96-04-07} and \cite{cj96-04-08} it was shown that both
quasi-growing grammars and quasi-growing context-sensitive grammars
characterize the class of growing context-sensitive languages (also
see \cite{cj96-04-20})\@. Instead of valuating only the symbols, we
can also valuate their positions inside a rule\@. A position valuation
is a function that is defined for an initial segment of the natural
numbers\@. It must valuate at least one position\@. In the following
we will refer to \(\max\{\strlength{\alpha},\strlength{\beta}\}\) as
\emph{the order of the rule} \(\alpha\to\beta\), and to
\(\gramord(G)\equdef\max\setof{\max\{\strlength{\alpha},\strlength{\beta}\}}%
{(\alpha\to\beta)\in P}\) as \emph{the order of} \(G\)\@. Note that in
the case of a context-sensitive grammar the order of \(G\) is equal to
\(\max\setof{\strlength{\beta}}{(\alpha\to\beta)\in P}\)\@. By ``a
normal form of order 2,'' we mean a normal form such that every
grammar in this normal form has order at most~2\@.
%
\begin{alabsubtext}{Definition}{1}{}
%
A \emph{position valuation} is a function
\(s\oftype\funcspace{\universe{N}^{+}}{\universe{N}^{+}}\) with:
%
\begin{quote}
%
If \(s\) is defined for a \(j\in\universe{N}^{+}\), then \(s\) is also
defined for every \(i\in\universe{N}^{+}\) with \({i<j}\)\@.
%
\end{quote}
\sentence
%
If \(s\) is defined for all \(i\in\universe{N}^{+}\), we say \(s\) is an 
\emph{infinite} position valuation---in the other case, 
\(s\) is a \emph{finite} position valuation\@.
We call each \(i\in\universe{N}^{+}\) where \(s(i)\) is defined a
\emph{valuated position of}~\(s\)\@.
%
\end{alabsubtext}
%
\apar{2-10}
It is also possible to allow zero points for position valuations, but
with the techniques used to show our main results we get for each
position valuation with zero points a characterization of
\(\classoflang{CSL}\) (see Theorem~8)\@. We restrict ourselves to the
most interesting position valuations which have at least two valuated
positions\@.
%
\begin{alabsubtext}{Definition}{2}{}
%
Let \(s\) be a position valuation\@. A grammar \(G =\langle
N,T,S,P\rangle\) is called \emph{weakly growing context-sensitive
related to the position valuation \(s\)} or also \emph{\(s\)-weakly
growing context-sensitive}, if the following hold:
%
\begin{enumerate}
%
\item[(i)] \(G\) is context-sensitive\@.
%
\item[(ii)] Let \(l\) be the order of \(G\)\@. Then \(s\) has at least \(l\) 
valuated positions\@.
%
\item[(iii)] There exists a function
\(f\oftype\funcspace{N\setunion T}{\universe{N}}\) such that for 
every rule
\((\alpha_{1}\dots\alpha_{n}\to\beta_{1}\dots\beta_{m})\in P\setminus
\{(S\to\emptystring)\}\) it holds that
%
\begin{aequation}{\asteqnmark}
%
\sum_{i=1}^{n}s(i)\mult f(\alpha_{i})<\sum_{i=1}^{m}s(i)\mult f(\beta_{i})
%
\end{aequation}
%
Such a function \(f\) is called a \emph{symbol valuation for} \(G\)\@.
If the inequality (\asteqnmark) above holds for a rule
\((\alpha\to\beta)\in P\), we say \(\alpha\to\beta\) is
\emph{\(s\)-weakly growing with~\(f\)}\@.
%
\end{enumerate}
\sentence
%
The sets of corresponding grammars and languages are denoted by 
\(\classofgrammar{WGCSG}_{s}\) and \(\classoflang{WGCSL}_{s}\),
respectively\@.
%
\end{alabsubtext}
%
\apar{2-11}
As we now valuate not only the symbols but also their positions inside
a rule, it is possible to interchange two symbols by a rule\@. This
can be used to show that the language
\(\flanguage{COPY}\equdef\setof{ww}{w\in\{a,b\}^{*}}\) is weakly growing 
context-sensitive related to every nonconstant position
valuation\@. To give an intuition of weakly growing context-sensitive
grammars, we look at the following example closely\@.
%
\begin{alabsubtext}{Example}{1}{}
\exampfontshape
%
\apar{Example 1-1}
Consider the language \(\flanguage{COPY}\equdef\setof{ww}{w\in\{a,b\}^{*}}\)\@.
Let \(s\) be any position valuation with at least two valuated positions 
and \({s(1)<s(2)}\)\@.
%
\apar{Example 1-2}
Define a grammar \(G=\langle N,\{a,b\},S,P\rangle\) as follows:
%
\[N\equdef\left\{S,\tilde{S},A,A',B,B',(X,a),(X,b)\right\}\]
%
and \(P\) contains the following rules:
%
\begin{alignat*}{4}
%
S &\to\emptystring & S &\to\tilde{S} & & & & \\
%
\tilde{S} &\to AA'\tilde{S} \qquad & A'A &\to AA' \qquad &
A'(X,a) &\to (X,a)a \qquad & (X,a) &\to a\\
%
\tilde{S} &\to BB'\tilde{S} \qquad & A'B &\to BA' \qquad &
A'(X,b) &\to (X,a)b \qquad & (X,b) &\to b\\
%
\tilde{S} &\to A(X,a) \qquad & B'A &\to AB' \qquad &
B'(X,a) &\to (X,b)a \qquad & A &\to a\\
%
\tilde{S} &\to B(X,b) \qquad & B'B &\to BB' \qquad &
B'(X,b) &\to (X,b)b \qquad & B &\to b
%
\end{alignat*}
\sentence
%
This grammar is context-sensitive, of order \(2\), and it generates
the language \(\flanguage{COPY}\)\@. Now we define
\(f\oftype\funcspace{N\setunion T}{\universe{N}}\)~by:
%
\begin{align*}
%
f(\tilde{S}) &\equdef 1\\
%
f(S) &\equdef f(A)\equdef f(B)\equdef f((X,a))\equdef f((X,b))\equdef 2\\
%
f(A') &\equdef f(B')\equdef 3\\
%
f(a) &\equdef f(b)\equdef 3
%
\end{align*}
\sentence
%
With a simple calculation it can be seen that every rule of \(P\) is 
\(s\)-weakly growing with respect to this symbol valuation\@.
Thus the grammar \(G\) is \(s\)-weakly growing context-sensitive\@.
%
{\nopagebreakbeginpar\markendlst{Example 1}}
\end{alabsubtext}
%
\apar{2-12}
As \(\flanguage{COPY}\notin\classoflang{GCSL}\) \cite{cj96-04-05}, we
have \(\classoflang{WGCSL}_{s}\not\subseteq\classoflang{GCSL}\) for
every nonconstant position valuation \(s\)\@. (The example above can
be adapted easily for position valuations \(s\) with \(s(1)>s(2)\) and
for those with a constant beginning part\@.)
%
\apar{2-13}
Note that if we use classical context-sensitive grammars in the
definition of weakly growing context-sensitive grammars, we get a
subclass of \(\classofgrammar{GCSG}\) \cite{cj96-04-22}\@. Here the
interesting question arises as to whether this class of grammars
already characterizes the class \(\classoflang{GCSL}\)\@. On the other
hand, it can easily be seen that it is not possible to interchange two
symbols back and forth in the same grammar; thus we know
\(\classofgrammar{WGCSG}_{s}\subset\classofgrammar{CSG}\) for every
position valuation~\(s\)\@.
%
\apar{2-14}
We now look briefly at some robustness properties of the definition of
weakly growing context-sensitive languages\@. As can easily be seen,
the standard algorithm to delete chain rules (see, e.g.,
\cite{cj96-04-16}) can be adapted for weakly growing context-sensitive
grammars\@. The same applies to the standard algorithm to delete
terminal symbols from the left-hand side of a rule\@. Thus we obtain:
%
\begin{alabsubtext}{Proposition}{1}{}
%
\apar{Proposition 1-1}
For every \(\classofgrammar{WGCSG}\) related to a position valuation \(s\),
there exists an equivalent \(\classofgrammar{WGCSG}_{s}\) without 
chain rules, even if there is only a symbol valuation known 
such that some chain rules are not strictly growing, 
i.e., cycling with chain rules can be deleted in such cases\@.
%
\apar{Proposition 1-2} 
Furthermore, in a \(\classofgrammar{WGCSG}_{s}\),
terminals can be forbidden on the left-hand side of rules
without affecting the grammar's inherent power\@.
%
\end{alabsubtext}
\sentence
%
\apar{2-15}
In an inequality, the multiplication of both sides with the same
positive value does not affect its validity, and the following holds\@.
%
\begin{alabsubtext}{Proposition}{2}{}
%
For all \(k\in\universe{Q}^+\), the classes
\(\classoflang{WGCSL}_{k\mult s}\) are the same\@.
%
\end{alabsubtext}
%
\apar{2-16}
Thus, for each constant position valuation \(C\), it holds that
\(\classofgrammar{WGCSG}_{C}=\classofgrammar{QGCSG}\) and 
consequently, \(\classoflang{WGCSL}_{C}=\classoflang{GCSL}\)\@.
%
\apar{2-17}
The values on both sides of an inequality can not only be stretched,
but can also be shifted without affecting its validity, which leads to
the following result\@.
%
\begin{alabsubtext}{Lemma}{1}{}
%
In Definition~2 (iii) it is sufficient to demand that there exists a
function \(f\oftype\funcspace{N\setunion T}{\universe{Q}}\), i.e.,
with values in \(\universe{Q}\), that satisfies the
inequality~(\asteqnmark)\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{1}{}
\prooffontshape
%
\apar{Proof of Lemma 1-1}
Let \(s\) be a position valuation and let
\(G=\langle N,T,S,P\rangle\) be a context-sensitive grammar where 
\(s\) has at least \(\gramord(G)\) valuated positions\@.
Let \(f\oftype\funcspace{N\setunion T}{\universe{Q}}\) be a symbol
valuation such that for every rule
\((\alpha_{1}\dots\alpha_{n}\to\beta_{1}\dots\beta_{m})\in P\)
not equal to \((S\to\emptystring)\), it holds that
%
\[\sum_{i=1}^{n}s(i)\mult f(\alpha_{i})<\sum_{i=1}^{m}s(i)\mult f(\beta_{i})\]
\sentence
%
Let \(\{a_{1},\dots,a_{k}\}\) be the set of symbols \(N\setunion T\) and 
\(f(a_{i})=\frac{p_{i}}{q_{i}}\) with \(p_{i}\in\universe{Z}\) 
and \(q_{i}\in\universe{N}^{+}\) for \(i=1,\dots,k\)\@. With an easy
transformation we obtain a symbol valuation with symbols in
\(\universe{N}\): Let \(q\equdef\lcm(q_{1},\dots,q_{k})\) be the common
denominator of all values and
\(z\equdef q\mult\absvalue{\min\{0,p_{1},\dots,p_{k}\}}\) be the
product of this common denominator with the absolute value of the
smallest negative enumerator\@. Then by a linear transformation we
obtain natural numbers: \(f'(a_{i})\equdef q\mult f(a_{i})+z\)\@. The
inequalities still apply, as the grammar has no length-decreasing
rules\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 1}}
\end{alabsubtext}
%
\apar{2-18}
In a similar way, it can be seen that allowing values out of
\(\universe{Q}^{+}\) for position valuations does not lead to any new
language classes\@.
%
\apar{2-19}
As we mentioned above, in the case of quasi-growing context-sensitive
grammars, if we omit the requirement of context-sensitivity, we obtain
grammars that characterize the same language class
\cite{cj96-04-07}\@. In the case of weakly growing context-sensitive
grammars, the effect is different: If in Definition~2 we leave out the
requirement of context-sensitivity, we obtain the weakly growing
grammars, which already characterize the languages generated by
nonrestricted grammars \cite{cj96-04-21}, i.e., the class of
recursively enumerable sets\@.
%
\apar{2-20}
To lead to our main results we now introduce the two cases of steady and 
unsteady position valuations\@.
%
\begin{alabsubtext}{Definition}{3}{}
%
\apar{Definition 3-1}
A position valuation
\(s\oftype\funcspace{\universe{N}^{+}}{\universe{N}^{+}}\) is called 
\emph{steady} if it coincides with an exponential function on its domain, 
that is, if it can be written~as
%
\[s(i)=s(1)\mult\growthfactor{w}(s)^{i-1}\]
%
where \(\growthfactor{w}(s)\equdef\frac{s(2)}{s(1)}\), so
\(\growthfactor{w}(s)\in\universe{Q}^{+}\)\@. This fraction,
\(\growthfactor{w}(s)\), is called the \emph{growth factor of}~\(s\)\@.
%
\apar{Definition 3-2}
In the other case, \(s\) is \emph{unsteady}\@. Note that this is the
case if and only if \(s\) has at least three valuated positions, and
if there exists a valuated position \(i\in\universe{N}^{+}\) of \(s\),
for which \(i-1\) and \(i+1\) are valuated, too, with:
%
\[s(i)^{2}\neq s(i-1)\mult s(i+1)\]
\sentence
%
In this case, we call such an \(i\) a \emph{blip of} \(s\), and the
smallest such \(i\) we call the \emph{first blip of}~\(s\)\@.
%
\end{alabsubtext}
%
\apar{2-21}
Note that \(\growthfactor{w}(s)<1\) means \(s\) is monotone decreasing, 
and \(\growthfactor{w}(s)=1\) means \(s\) is constant\@.
%
{\nopagebreakendpar
%
\begin{alabsubtext}{Definition}{4}{}
%
Let \(s\) be a position valuation\@. Let
\(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\), and let
\(f\) be an appropriate symbol valuation for \(G\)\@. The \emph{growth
rate of a rule}
\((\alpha_{1}\dots\alpha_{n}\to\beta_{1}\dots\beta_{m})\in P\) 
with respect to \(f\) is the difference
\(\sum_{i=1}^{m}s(i)\mult f(\beta_{i})-\sum_{i=1}^{n}s(i)\mult f(\alpha_{i})\)
between the values on the right-hand and the left-hand sides of the
rule\@. The \emph{growth rate of a derivation step}
\(u_{1}\dots u_{n}\derives{G}v_{1}\dots v_{m}\) with respect to \(f\)
is the difference
\(\sum_{i=1}^{m}s(i)\mult f(v_{i})-\sum_{i=1}^{n}s(i)\mult f(u_{i})\)
between the values of \(v_{1}\dots v_{m}\) and \({u_{1}\dots u_{n}}\)\@.
%
\end{alabsubtext}
}
%
\apar{2-22}
The relationship between the growth rate of a rule, the growth rate of
a derivation step, and the growth factor (in case of a steady position
valuation) is investigated in Lemma~3 and Lemma~5\@. Nevertheless, we
first look at general properties of weakly growing context-sensitive
languages\@.
%
\asection{3}{Closure Properties and Normal Form} 
%
\apar{3-1}
The most important closure properties are the
\(\classofclassoflang{AFL}\) properties\@. It turns out that
steadiness of a position valuation has no effect on these closure
properties except for one (see Section~3.1)\@. To the contrary,
unsteadiness does affect the transformability of a weakly growing
context-sensitive grammar into an equivalent grammar of the same type
in normal form of order~2 (see Section~3.2)\@. In Section~6
(Theorem~10), we will prove that the existence of one missing closure
property (inverse homomorphism) for the weakly growing
context-sensitive languages with steady position valuation is
equivalent to the existence of a transformation into a normal form of
order~2 for weakly growing context-sensitive grammars with unsteady
position valuation\@.
%
\asubsection{3.1}{Closure Properties}
%
\apar{3.1-1}
To get to know a new language class more closely, it is useful to
learn something about its closure properties\@. Clearly, the closure
under non-\(\emptystring\)-free homomorphism of
\(\classoflang{WGCSL}_{s}\) yields the class of all recursively
enumerable (r.e.) sets for every position valuation \(s\), i.e.,
\(\classoflang{WGCSL}_{s}\) is a basis for the class of r.e.\ sets
(originally introduced by Raymond Smullyan in \cite{cj96-04-29}; see
also \cite{cj96-04-06})\@. With standard arguments, we show the
following\@.
%
\begin{alabsubtext}{Theorem}{1}{}
%
Let \(s\) be a position valuation with at least two valuated
positions\@. \(\classoflang{WGCSL}_{s}\) is closed under
\(\emptystring\)-free homomorphism, union, \(\emptystring\)-free
regular substitution, concatenation, and intersection with regular
sets\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{1}{}
\prooffontshape\ \relax
%
\paragraph{For \protect\(\boldsymbol{\emptystring}\protect\)-free
homomorphism:}
%
\apar{Proof of Theorem 1-1}
Let \(G =\langle N,T,S,P\rangle\in\classoflang{WGCSL}_{s}\), and let
\(f\) be a symbol valuation for \(G\)\@. Let
\(h\oftype\funcspace{T}{\Delta}\) be an \(\emptystring\)-free homomorphism\@.
%
\apar{Proof of Theorem 1-2}
A grammar \(G'=\langle N',\Delta,S,P'\rangle\) for
\(h(\gramtolang(G))\) can be constructed by defining
\(N'\equdef N\setunion T\) and adding to \(P\) the rules
\((a\to h(a))\) for every \(a\in T\) to obtain \(P'\)\@. An appropriate
symbol valuation can be found by extending \(f\) to \(\Delta\) with
\(f(u)=\max\setof{f(a)}{a\in T}+1\) for \({u\in\Delta}\)\@.
%
\paragraph{For union:}
%
\apar{Proof of Theorem 1-3}
Let \(G_{1}=\langle N_{1},T_{1},S_{1},P_{1}\rangle\)
and \(G_{2}=\langle N_{2},T_{2},S_{2},P_{2}\rangle\) be in
\(\classoflang{WGCSL}_{s}\)\@. Let \(f_{1}\) and \(f_{2}\) be
appropriate symbol valuations for \(G_{1}\) and \(G_{2}\),
respectively\@. Wlog we can assume
\((N_{1}\setunion T_{1})\setintsct N_{2}=\emptyset\) and
\(N_{1}\setintsct(N_{2}\setunion T_{2})=\emptyset\)\@. A grammar
\(G=\langle N,T_{1}\setunion T_{2},S,P\rangle\) for
\(\gramtolang(G_{1})\setunion\gramtolang(G_{2})\) can be constructed
by \(N=N_{1}\setunion N_{2}\setunion\{S\}\) and \(P=P_{1}\setunion
P_{2}\setunion\{(S\to S_{1}),(S\to S_{2})\}\)\@. (Handling the case
\(\emptystring\in \gramtolang(G_{1})\setunion \gramtolang(G_{2})\) is
standard\@.) An appropriate symbol valuation \(f\) is defined by
\(\restrfun{f}{N_{1}\setunion T_{1}}\equdef 2\mult f_{1}\),
\(\restrfun{f}{N_{2}\setunion T_{2}}\equdef 2\mult f_{2}\),
\({f(S)\equdef 1}\)\@.
%
\paragraph{For \(\boldsymbol{\emptystring}\)-free regular substitution:}
%
\apar{Proof of Theorem 1-4}
In fact, we can show that \(\classoflang{WGCSL}_{s}\) is closed under
\(\emptystring\)-free \(\classoflang{WGCSL}_{s}\) substitution\@. Then,
closure under \(\emptystring\)-free regular substitution follows,
because every regular grammar is also weakly growing
context-sensitive\@. Just use the symbol valuation
\(f\oftype\funcspace{N\setunion T}{\universe{N}^{+}}\) defined by
\(f(A)\equdef 1\) for \(A\in N\), \(f(a)\equdef 2\) for \({a\in T}\)\@.
%
\apar{Proof of Theorem 1-5}
To show closure under \(\emptystring\)-free \(\classoflang{WGCSL}_{s}\)
substitution, we consider
\(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\), and for
every \(a\in T\) let
\(G_{a}=\langle N_{a},T_{a},S_{a},P_{a}\rangle\in\classofgrammar{WGCSG}_{s}\),
where we can assume wlog that for every \(a\) and \(b\) in \(T\) with
\(a\neq b\), it holds that \((N_{a}\setunion T_{a})\setintsct
N_{b}=\emptyset\), and that terminals only appear on the right-hand
side of rules (Proposition~1)\@. Let \(f\) and \(f_{a}\) for \(a\in T\)
be appropriate symbol valuations, respectively\@. Let
\({L_{a}\equdef\gramtolang(G_{a})}\)\@.
%
\apar{Proof of Theorem 1-6}
Now we construct a grammar \(G'=\langle N',T',S,P'\rangle\) for the
language
%
\[L=\setof{w}{\text{ there exists }v=a_{1}\dots a_{n}\in L
\text{ with }w\in L_{a_{1}}\mult\dots\mult L_{a_{n}}}\]
\sentence
%
Let
%
\begin{align*}
%
N' &\equdef N\setunion\sunionofset{a\in T}{N_{a}}\\
%
T' &\equdef\sunionofset{a\in T}{T_{a}}\\
%
P' &\equdef
%
\begin{aligned}[t]
%
&\left(P\setminus\setof{(A\to a)}{A\in N,a\in T}\right)\setunion\\
%
&\setof{A\to S_{a}}{(A \to a)\in P}\setunion\sunionofset{a\in T}{P_{a}}
%
\end{aligned}
%
\end{align*}
\sentence
%
What happens is that every original terminal is taken as a start
symbol for the grammar of the substituting language\@.
The function
%
\[f'\oftype\funcspace{N\setunion\bigcup_{a\in T}(N_{a}\setunion
T_{a})}{\universe{N}^{+}}\]
 defined~by
%
\begin{align*}
%
\restrfun{f'}{N} &\equdef f\\
%
\restrfun{f'}{N_{a}\setunion T_{a}} &\equdef
  \max\setof{f(b)}{b\in T}\mult f_{a}\text{ for }a\in T
%
\end{align*}
%
is an appropriate symbol valuation for \(G'\)\@.
%
\paragraph{For concatenation:}
%
\apar{Proof of Theorem 1-7}
Let \(G_{1}=\langle N_{1},T_{1},S_{1},P_{1}\rangle\)
and \(G_{2}=\langle N_{2},T_{2},S_{2},P_{2}\rangle\) be in
\(\classoflang{WGCSL}_{s}\)\@. Let \(f_{1}\) and \(f_{2}\) be
appropriate symbol valuations for \(G_{1}\) and \(G_{2}\), respectively\@.
%
\apar{Proof of Theorem 1-8}
Wlog~we can assume \((N_{1}\setunion T_{1})\setintsct
N_{2}=\emptyset\) and
\(N_{1}\setintsct(N_{2}\setunion T_{2})=\emptyset\), and that
terminals only appear on the right-hand side of rules
(Proposition~1)\@. A grammar \(G=\langle N,T_{1}\setunion
T_{2},S,P\rangle\) for
\(\gramtolang(G_{1})\catlang\gramtolang(G_{2})\) can be constructed by
defining \(N\equdef N_{1}\setunion N_{2}\setunion\{S\}\) and
\(P\equdef P_{1}\setunion P_{2}\setunion\{(S\to S_{1}S_{2})\}\)\@.
(Handling the cases
\(\emptystring\in\gramtolang(G_{1})\) and
\(\emptystring\in\gramtolang(G_{2})\)is standard\@.) An appropriate
symbol valuation \(f\) is found by joining \(f_{1}\) and \(f_{2}\) and
defining \({f(S)\equdef 1}\)\@.
%
\paragraph{For intersection with regular sets:}
%
\apar{Proof of Theorem 1-9}
Let \(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\),
let \(L\) be a regular set, and let \(M=(Q,\Sigma,q_{0},\delta,F)\) be
a deterministic finite automaton that accepts~\(L\)\@.
%
\apar{Proof of Theorem 1-10}
By Proposition~1, we can assume that there appear only nonterminals in
the left-hand sides of the rules in \(G\)\@. A grammar \(G'=\langle
N',T\setintsct\Sigma,S',P'\rangle\) for \(L\setintsct \gramtolang(G)\)
is constructed as follows:
\(N'\equdef\setof{(p,A,q)}{p,q\in Q,A\in N}\setunion\{S'\}\)
(so the nonterminals are triples), and \(P\) contains the following rules
(for every \(A_{1},\dots,A_{n}\), \(B_{1},\dots,B_{m}\in N\),
\(u_{0},\dots,u_{m+1},w\in(\Sigma\setintsct T)^{*}\), and
\(q_{1},\dots,q_{n+1},p_{1},\dots,p_{m},p'_{1},\dots,{p'_{m}\in Q}\)):
%
\begin{alignat*}{3}
%
&S'\to & &w \quad & \text{if } &(S\to w)\in P\text{ and }w\in L\\
%
&S'\to & &\lefteqn{u_{0}(p_{1},B_{1},p_{1}')u_{1}(p_{2},B_{2},p_{2}')
\dots u_{m-1}(p_{m},B_{m},p_{m}')u_{m}} & & \\
%
& & & & \text{if } &(S'\to u_{0}B_{1}u_{1}B_{2}\dots
u_{m-1}B_{m}u_{m})\in P\text{ and}\\
%
& & & & &\delta^{*}(q_{0},u_{0})=p_{1}\text{ and}\\
%
& & & & &\delta^{*}(p_{i}',u_{i})=p_{i+1}
  \text{ for }i=1,\dots,m-1\text{ and}\\
%
& & & & &\delta^{*}(p_{m}',u_{m})\in F \\
%
&\lefteqn{(q_{1},A_{1},q_{2})(q_{2},A_{2},q_{3})\dots
(q_{n},A_{n},q_{n+1})\to} & & & & \\
%
& & &\lefteqn{u_{1}(p_{1},B_{1},p_{1}')u_{2}(p_{2},B_{2},p_{2}')\dots
u_{m}(p_{m},B_{m},p_{m}')u_{m+1}} & & \\
%
& & & & \text{if } &(A_{1}A_{2}\dots A_{n}\to u_{1}B_{1}u_{2}B_{2}\dots
u_{m}B_{m-1}u_{m+1})\in P\text{ and}\\
%
& & & & &\delta^{*}(q_{1},u_{1})=p_{1}\text{ and}\\
%
& & & & &\delta^{*}(p_{i}'\text{, }u_{i+1})=p_{i+1}\text{ for }
  i=1,\dots,m-1\text{ and}\\
%
& & & & &\delta^{*}(p_{m}',u_{m+1})=q_{n+1}\\
%
&\lefteqn{(q_{1},A_{1},q_{2})(q_{2},A_{2},q_{3}) \dots
(q_{n},A_{n},q_{n+1})\to w} & & & & \\
%
& & & & \text{ if } &(A_{1}A_{2}\dots A_{n}\to w)\in P\text{ and }
\delta^{*}(q_{1},w)=q_{n+1} 
%
\end{alignat*}
\sentence
%
(This construction is due to \cite{cj96-04-14}\@.
Matthias Jantzen uses this to show the same result for
\(\classoflang{GCSL}\)~\cite{cj96-04-18}\@.)
%
\apar{Proof of Theorem 1-11}
The function \(f\oftype\funcspace{N}{\universe{N}^{+}}\) defined by
%
\begin{xalignat*}{2}
%
f'((p, A, q)) &\equdef f(A) & &\text{for }p,q\in Q,\text{ }A\in N \\
%
f'(S') &\equdef f(S) & & \\
%
f'(a) &\equdef f(a) & &\text{for }a\in T 
%
\end{xalignat*}
%
is an appropriate symbol valuation for~\(G'\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Theorem 1}}
\end{alabsubtext}
%
\apar{3.1-2}
We have proved the \(\classofclassoflang{AFL}\) properties (except the
closure under inverse homomorphism)\@. Now we show the closure under
transposition\@. We will use this result in the proof of Theorem~4,
where we show an important property concerning steady position
valuations\@.
%
\begin{alabsubtext}{Theorem}{2}{}
%
Let \(s\) be a nonconstant position valuation\@. 
Then \(\classoflang{WGCSL}_{s}\) is closed under transposition\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{2}{}
\prooffontshape
%
\apar{Proof of Theorem 2-1}
We sketch the idea for the case \({s(1)<s(2)}\)\@.
%
\apar{Proof of Theorem 2-2}
For a grammar \(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\),
a grammar \(\tilde{G}=\langle\tilde{N},T,\tilde{S},\tilde{P}\rangle\)
is constructed as follows:
%
\[\tilde{N}\equdef N\setunion\{\tilde{S}\}\setunion\setof{a'}{a\in T}\setunion
\setof{\check{X}}{X\in N}\setunion\setof{\check{a}}{a\in T}\]
%
where the rules in \(\tilde{P}\) accomplish the following:
%
\begin{quote}
%
First, for a word \(w=w_{1}\dots w_{n}\in L\), the sentential form
\(\check{w}_{1} w_{2}'\dots w_{n}'\) is generated (for this, 
appropriate copies of the rules in \(P\) are used)\@. 
Then this sentential form is transformed with rules of the form
%
\begin{align*}
%
\check{a}b' &\to \check{b}a \\
%
a b' &\to b'a \\
%
\check{a} &\to a
%
\end{align*} 
%
into the word \(w_{n}\dots w_{1}\)\@.
%
\end{quote}
\sentence
%
Clearly \(\gramtolang(\tilde{G})=\gramtolang(G)^{T}\)\@. Out of a
symbol valuation \(f\) for \(G\) an appropriate symbol valuation for
\(\tilde{G}\) can be constructed in the following way\@.
%
\apar{Proof of Theorem 2-3}
Define \(\tilde{f}\oftype\funcspace{\tilde{N}}{\universe{N}^{+}}\)~by
%
\begin{alignat*}{4}
%
\tilde{f}(X) &\equdef f(X) & \quad &\text{for }X\in N \qquad &
\tilde{f}(\check{X}) &\equdef f(X) & \quad &\text{ for }X\in N\\
%
\tilde{f}(a') &\equdef f(a) & \quad &\text{for }a\in T \qquad & 
\tilde{f}(\check{a}) &\equdef f(a) & \quad &\text{for }a\in T\\
%
\tilde{f}(\tilde{S}) &\equdef f(S) & & &
\tilde{f}(a) &\equdef\lefteqn{\max\setof{f(a)}{a\in T}+1} & &
%
\end{alignat*}
\sentence
%
\apar{Proof of Theorem 2-4}
For a symbol valuation \(s\) with \(s(1)>s(2)\), the proof works
analogously\@. For the case of a nonconstant position valuation with
\(s(1)=s(2)\), this idea can be adapted by shifting the ``mirror
point'' \(\check{X}\) and treating the borders appropriately\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Theorem 2}}
\end{alabsubtext}
%
\apar{3.1-3}
To show that \(\classoflang{WGCSL}_{s}\) is an
\(\classofclassoflang{AFL}\) for a certain position valuation \(s\),
we would have to show that \(\classoflang{WGCSL}_{s}\) is closed under
inverse homomorphism (or under \(k\)-bounded homomorphism because of
Theorem~1, and from \cite{cj96-04-14} we know that both closure
properties are equivalent under the assumption that the closure
properties named in Theorem~1 apply)\@.
%
\apar{3.1-4}
For steady position valuations, this problem is equivalent to the
problem of whether all linear space-bounded automata can be simulated
by linear space-bounded automata with an additional universal
exponential time bound (see Theorem~10)\@. The reason for this
equivalence lies in the fact that for every position valuation, the
closure under inverse homomorphisms of
\(\classoflang{WGCSL}_{s}\) equals \(\classoflang{CSL}\)
(see Theorems 5 and~9)\@.
%
\asubsection{3.2}{Normal Form}
%
\apar{3.2-1}
In Section~2 we introduced the two cases of steady and unsteady
position valuations\@. Now we work out what we can say about the
transformability of corresponding weakly growing context-sensitive
grammars into a normal form of order~2\@.
%
\apar{3.2-2}
For every steady position valuation \(s\), each grammar in
\(\classofgrammar{WGCSG}_{s}\) can be transformed into a normal form
of order 2\@. We will use Cremers normal form \cite{cj96-04-12}\@.
Compared with all other normal forms of order~2, the advantage of
Cremers normal form lies in its minimal number of different types of
rules\@. Moreover, with the probably more popular normal form proposed
by Kuroda, we can only describe classical context-sensitive grammars,
which leads here to a language class contained in
\(\classoflang{GCSL}\), as we mentioned in Section~2\@.
%
\begin{alabsubtext}{Definition}{5}{\protect\cite{cj96-04-12}}
%
A context-sensitive grammar \(G=\langle N,T,S,P\rangle\) is in 
\emph{Cremers normal form} if every rule in \(P\) is of one of the
forms \(AB\to CD\), \(A\to CD\), or \(A\to a\), where \(A,B,C,D\in N\), 
\({a\in T}\)\@.
%
\end{alabsubtext}
%
\apar{3.2-3}
At first, we adapt the obvious algorithm to reduce the order of a
grammar\@.
%
\begin{alabsubtext}{Lemma}{2}{}
%
Let \(s\) be a steady position valuation\@. Then for every grammar
\(G\in\classofgrammar{WGCSG}_{s}\) of order \(l\geq 3\), there exists
an equivalent grammar \(G'\in\classofgrammar{WGCSG}_{s}\) of
order~\({l-1}\)\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{2}{}
\prooffontshape
%
\apar{Proof of Lemma 2-1}
Let \(s\oftype\funcspace{\universe{N}^{+}}{\universe{N}^{+}}\) be a
steady position valuation with at least three valuated positions (in
the other case there is nothing to show)\@. Define
\(s'\oftype\funcspace{\universe{N}^{+}}{\universe{N}^{+}}\) by
\(s'(i)\equdef s(i+1)\) for all \(i\in\universe{N}^{+}\), that is, if
\(s(i+1)\) is undefined, so is \(s'(i)\)\@. Let
\(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\) be of order
\(l\geq 3\), let \(f\oftype\funcspace{N\setunion T}{\universe{N}}\) be
a symbol valuation for~\(G\)\@.
%
\apar{Proof of Lemma 2-2}
We now construct a grammar \(G'=\langle N',T,S',P'\rangle\) and a
symbol valuation \(f'\oftype\funcspace{N'\setunion T}{\universe{Q}}\)
by the following algorithm:
%
\begin{algorithm}{informal}{}
%
\begin{enumerate} 
%
\item[1.] \(N'\assigned N\), \(P'\assigned\emptyset\).
%
\item[2.] \(f'(A)\assigned f(A)\) for every \(A\in N\),
\(f'(a)\assigned f(a)\) for every \({a\in T}\).
%
\item[3.] For every rule 
\((\alpha_{1}\dots\alpha_{n}\to\beta_{1}\dots\beta_{m})\in P\),
execute the following:
%
\begin{enumerate}
%
\item[4.] If \(m\leq 2\), then
\(P'\assigned
  P'\setunion\{(\alpha_{1}\dots\alpha_{n}\to\beta_{1}\dots\beta_{m})\}\).
%
\item[5.] If \(3\leq m\leq l\), then let \(X\) be a new nonterminal
symbol, \({X\notin N'}\).
%
\begin{enumerate}
%
\item[6.] Define the rules:
%
\begin{alignat*}{2}
%
&\rulename{(R1)} \quad & \alpha_{1}\alpha_{2} &\to\beta_{1}X \\
%
&\rulename{(R2)} \quad & X\alpha_{3}\dots\alpha_{n}&\to\beta_{2}\dots\beta_{m}
%
\end{alignat*}
%
\comment{Here \(n=2\), which means \(\alpha_{3}\dots\alpha_{n}=\emptystring\), 
or \(n=1\), which means additionally \(\alpha_{2}=\emptystring\) is possible.}
%
\item[7.] \(P'\assigned P'\setunion\{\rulename{(R1)},\rulename{(R2)}\}\).
%
\item[8.] \(f'(X)\assigned\frac{s(1)}{s(2)}\mult f(\alpha_{1})+f(\alpha_{2}) 
-\frac{s(1)}{s(2)}\mult f(\beta_{1})+\frac{1}{2\mult s(2)}\)
%
\end{enumerate}
%
\end{enumerate}
%
\end{enumerate}
%
\end{algorithm}
\sentence
%
It holds that \(\gramtolang(G') = \gramtolang(G)\)\@. As \(G\) is
context-sensitive, so is \(G'\)\@. By calculation and Lemma~1
it can be shown that \(G'\in\classofgrammar{WGCSG}_{s'}\)\@.
By Proposition~2 this implies \(G'\in\classofgrammar{WGCSG}_{s}\) 
(since \(s(i)=\growthfactor{w}(s)\mult s'(i)\) for every
\({i\in\universe{N}^{+}}\))\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 2}}
\end{alabsubtext}
%
\apar{3.2-4}
For unsteady position valuations, this algorithm and similar ones do
not work\@. This can be checked looking at the following interesting
example\@.
%
\begin{alabsubtext}{Example}{2}{}
\exampfontshape
%
Let \(s=\identfunc\), i.e., \(s(i)=i\) for every \(i\in\universe{N}^{+}\)\@.
Let \(\alpha_{1}\alpha_{2}\alpha_{3}\to\beta_{1}\beta_{2}\beta_{3}\)
be a rule, and let \(f(\alpha_{1})=1\), \(f(\alpha_{2})=1\),
\(f(\alpha_{3})=3\), \(f(\beta_{1})=1\), \(f(\beta_{2})=5\), and
\(f(\beta_{3})=1\)\@. Then the rule is\/ \(\identfunc\)-weakly growing
with \(f\), and in the rules \(\alpha_{1}\alpha_{2}\to\beta_{1} X\) 
and \(X\alpha_{3}\to\beta_{2}\beta_{3}\), the symbol \(X\) cannot be
valuated appropriately\@.
%
{\nopagebreakbeginpar\markendlst{Example 2}}
\end{alabsubtext}
%
\apar{3.2-5}
Lemma~2 can be applied step by step; thus together with Proposition~1
we obtain the following\@.
%
\begin{alabsubtext}{Theorem}{3}{}
%
Let \(s\) be a steady position valuation\@. For every grammar
\(G\in\classofgrammar{WGCSG}_{s}\), there exists an equivalent grammar
\(G'\in\classofgrammar{WGCSG}_{s}\) in Cremers normal form\@.
%
\end{alabsubtext}
%
\apar{3.2-6}
Thus for a steady position valuation \(s\), the class
\(\classoflang{WGCSL}_{s}\) is characterized by the growth factor
\(\growthfactor{w}(s)\) (this follows from Theorem~3
and Proposition~2)\@. We introduce the following notation:
%
\[\classoflang{WGCSL}_{\growthfactor{w}(s)}\equdef\classoflang{WGCSL}_{s}\]
\sentence
%
\apar{3.2-7}
When we treat steady position valuations, we can assume wlog that
\(s\) is an exponential function, or, if more convenient, that \(s\)
is a position valuation with only two valuated positions\@.
Additionally, we can assume that it is monotone increasing\@.
%
\begin{alabsubtext}{Theorem}{4}{}
%
Let \(s\) be a steady position valuation\@. Then
%
\[\classoflang{WGCSL}_{\growthfactor{w}(s)}=
\classoflang{WGCSL}_{\frac{1}{\growthfactor{w}(s)}}\]
\sentence
%
That is, having a position valuation \(s\), we can assume wlog it is
monotone increasing\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{4}{}
\prooffontshape
%
\begin{sloppypar}
\apar{Proof of Theorem 4-1}
Let \(s\) be a steady position valuation, let
\(G=\langle N,T,S,P\rangle\in\classoflang{WGCSL}_{s}=
\classoflang{WGCSL}_{\frac{s(2)}{s(1)}}\) be in Cremers normal form
(Theorem~3), and let \(f\) be a symbol valuation for
\(G\)\@. We define a grammar \(G'=\langle N,T,S,P'\rangle\), where
\(P'\) contains the transposed version of every rule in \(P\)\@.
Clearly, \(G'\) is context-sensitive and
\(\gramtolang(G')=\gramtolang(G)^{T}\)\@. Define a position valuation
\(s'\) by \(s'(1)\equdef s(2)\), \(s'(2)\equdef s(1)\)\@. If
\(G'\in\classofgrammar{WGCSG}_{s'}=
\classofgrammar{WGCSG}_{\frac{s(1)}{s(2)}}\),
then the claim follows from Theorem~2\@.
\end{sloppypar}
%
\apar{Proof of Theorem 4-2}
The transposed versions of the length-preserving rules clearly are
\(s'\)-weakly growing with respect to \(f\)\@. Now we look at the
expanding rules and define an appropriate symbol valuation \(f'\)
for~\(G'\)\@.
%
\apar{Proof of Theorem 4-3}
Consider a rule \((A\to BC)\in P\)\@. Then
\(s(1)\mult f(A)<s(1)\mult f(B)+s(2)\mult f(C)\)\@. If \(s(2)\mult
f'(A)<s(2)\mult f'(C)+s(1)\mult f'(B)\) holds, the rule \(A\to CB\) is
\(s'\)-weakly growing with respect to \(f'\)\@. We attach an additional
weight piece to \(B\) in order to fulfill this inequality, that is, we
define \(f'(B)\equdef f(B)+b\) where \(b\equdef
\frac{s(2)-s(1)}{s(1)}\mult m\) with \(m\geq f(A)\)\@. Attaching this
same weight piece to \(A\) and \(C\) does not affect the validity of
the given inequality\@.
%
\begin{sloppypar}
\apar{Proof of Theorem 4-4}
We define \(m\equdef\max\setof{f(A)}{A\in N}\), and define
\(f'\oftype\funcspace{N\setunion T}{\universe{Q}}\) by
%
\[f'(X)\equdef f(X)+\frac{s(2)-s(1)}{s(1)}\mult m
\text{ for }X\in N\setunion T\]
\sentence
%
Then every transposed version of an expanding rule in \(P\) is
\(s'\)-weakly growing with respect to \(f'\)\@. As \(f'\) differs from
\(f\) only by a constant addend, the transposed versions of the
length-preserving rules in \(P\) are \(s'\)-weakly growing with
respect to \(f'\) also\@. Thus \(G' \in \classofgrammar{WGCSG}_{s'}\)
follows from Lemma~1\@.
\end{sloppypar}
%
{\nopagebreakbeginpar\markendlst{Proof of Theorem 4}}
\end{alabsubtext}
%
\asection{4}{The Unsteady Position Valuation}
%
\apar{4-1}
In this section it is shown that
\(\classoflang{WGCSL}_{s}=\classoflang{CSL}\) for every unsteady
position valuation \(s\)\@. The only inclusion we have to show is
\(\classoflang{CSL}\subseteq\classoflang{WGCSL}_{s}\)\@.
%
\apar{4-2}
It is well known that linear-bounded automata characterize the
context-sensitive languages~\cite{cj96-04-19}\@. This will be used
extensively when we show the claim mentioned above\@. There the
following technique for simulating a linear-bounded automaton by a
context-sensitive grammar is adapted (see, e.g., \cite{cj96-04-16}):
We use a linear-bounded automaton that has a single tape, writes only
on the tape cells marked by the input, and makes no null moves\@. This
can be done without loss of generality (see, e.g., \cite{cj96-04-33},
\cite{cj96-04-16}, \cite{cj96-04-17})\@. Each configuration is
represented by a certain sentential form (see Figure~1)\@. We work on
three tracks, as follows\@. On the first track, we hold the input, on
the second track we always have the actual contents of the working
tape, and on the third track we have the actual state, put down
exactly below the symbol the linear-bounded automaton is actually
reading\@.
%
\begin{figure*}
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.135ex}%
%
\begin{picture}(600,145)(-20,645)
\thicklines
\put(140,780){\line( 1, 0){240}}
\put(140,760){\line( 1, 0){240}}
\put(180,780){\line( 0,-1){ 20}}
\put(200,780){\line( 0,-1){ 20}}
\put(206,770){\raisebox{0ex}[0ex][0ex]{ .  }}
\put(213.5,770){\raisebox{0ex}[0ex][0ex]{ .  }}
\put(221,770){\raisebox{0ex}[0ex][0ex]{ .  }}
\put(240,780){\line( 0,-1){ 20}}
\put(260,780){\line( 0,-1){ 20}}
\put(280,780){\line( 0,-1){ 20}}
\put(300,780){\line( 0,-1){ 20}}
\put(306,770){\raisebox{0ex}[0ex][0ex]{ .  }}
\put(314.5,770){\raisebox{0ex}[0ex][0ex]{ .  }}
\put(323,770){\raisebox{0ex}[0ex][0ex]{ .  }}
\put(340,780){\line( 0,-1){ 20}}
\put(360,780){\line( 0,-1){ 20}}
\put(270,730){\vector( 0, 1){ 20}}
\put( 30,690){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{sentential form:}}}
\put( 30,765){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{LBA:}}}
\put(280,735){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{state \(q\)}}}
\put(173,685){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ 
  \(\tapetriple{\text{i}}{\text{w}}{\omittapeentry}\)}}}
\put(205,685){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ o  }}}
\put(206,705){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ .  }}}
\put(213.5,705){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ .  }}}
\put(220,685){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ r  }}}
\put(221,705){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ .  }}}
\put(233,685){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ 
  \(\tapetriple{\text{n}}{\text{k}}{\omittapeentry} 
  \tapetriple{\text{p}}{\text{-}}{q}
  \tapetriple{\text{u}}{\text{t}}{\omittapeentry}\)}}}
\put(305,685){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ a  }}}
\put(306,705){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ .  }}}
\put(314.5,705){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ .  }}}
\put(322,685){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ p  }}}
\put(323,705){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ .  }}}
\put(338,685){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ 
  \(\tapetriple{\text{t}}{\text{e}}{\omittapeentry}\)}}}
\end{picture}}}
%
\afigcap{1}{Tape and sentential form (sketch)}
%
\end{figure*}
%
This sentential form is generated with the initial configuration with
an arbitrary input, then \(M\) is simulated step by step, and if \(M\)
accepts, the triples are transformed into the contents of their first
component, which then become terminal symbols\@.
%
\apar{4-3}
To simulate a context-sensitive grammar by a linear-bounded automaton,
we just follow a derivation step by step and compare the derived word
with the input afterwards\@.
%
\begin{sloppypar}
\apar{4-4}
As we mentioned earlier, for every unsteady position valuation \(s\),
\(\classoflang{WGCSL}_{s}=\classoflang{CSL}\)\@. To prove this, we use
that every unsteady position valuation \(s\) has a blip (see
Definition~3)\@. We distinguish four cases for an
unsteady position valuation \(s\), where \(j\) is the first blip:
\end{sloppypar}
%
\begin{enumerate}
%
\item[(i)] \(s(j-1)>s(j)\) and \(s(j)<s(j+1)\), that is, \(j\) is
a ``valley blip,''
%
\item[(ii)] \(s(j-1)<s(j)\) and \(s(j)>s(j+1)\), that is, \(j\) is
a ``peak blip,''
%
\item[(iii)] \(s\) is monotone increasing on an initial part up to the
position \(j+1\), and
%
\item[(iv)] \(s\) is monotone decreasing on an initial part up to the
position~\({j+1}\)\@.
%
\end{enumerate}
\sentence
%
Every unsteady position valuation corresponds to one of the cases
above\@. In each case we introduce for a linear-bounded automaton a way
of constructing an \(s\)-weakly growing context-sensitive grammar
following the algorithm mentioned above\@.
%
\paragraph{For the first case (i):}
%
\begin{sloppypar}
\apar{4-5}
Given a linear bounded automaton
\(M=(\Sigma,Q,\Gamma,q_{0},\delta,F)\), we construct the simulating
grammar \(G=\langle N,T,S,P\rangle\) as follows\@. \(N\) consists of
triples, where the first component contains an element of \(\Sigma\),
the second an element of \(\Gamma\), and the third is empty or
contains a state\@. Additionally, \(N\) contains marked copies of
those symbols for the right-hand and the left-hand borders\@. The idea
is to valuate (by an appropriately defined symbol valuation) all
triples without state with the same value, and the triples containing
a state with a greater value\@.
\end{sloppypar}
%
\apar{4-6}
The ``valley blip'' in the position valuation is then used as
follows\@.  In a rule that simulates a step of \(M\), the state
``moves'' following the move of the automaton's head\@. Thus, the
additional weight induced to a nonterminal by the state also
``moves,'' and by an appropriate left-hand context (that is, by
\(j-2\) preceding nonterminals for moving to the left, \(j-1\) for
moving to the right, where the position \(j\) is the ``valley blip''),
the rule is constructed so that on the left-hand side the state is
positioned exactly on that blip\@. In Figure~2 this is illustrated\@.
%
\begin{figure*}
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.135ex}%
%
\begin{picture}(600,175)(10,625)
\thicklines
\put(150,630){\circle*{5}}
\put(170,640){\circle*{5}}
\put(130,650){\circle*{5}}
\put(130,650){\line( 1,-1){ 20}}
\put(150,630){\line( 2, 1){ 20}}
\put(450,630){\circle*{5}}
\put(470,640){\circle*{5}}
\put(430,650){\circle*{5}}
\put(430,650){\line( 1,-1){ 20}}
\put(450,630){\line( 2, 1){ 20}}
\put(290,710){\vector( 1, 0){ 60}}
\put(370,780){\line( 1, 0){180}}
\put(370,760){\line( 1, 0){180}}
\put(380,780){\line( 0,-1){ 20}}
\put(400,780){\line( 0,-1){ 20}}
\put(420,780){\line( 0,-1){ 20}}
\put(440,780){\line( 0,-1){ 20}}
\put(460,780){\line( 0,-1){ 20}}
\put(480,780){\line( 0,-1){ 20}}
\put(500,780){\line( 0,-1){ 20}}
\put(520,780){\line( 0,-1){ 20}}
\put(540,780){\line( 0,-1){ 20}}
\put(430,730){\vector( 0, 1){ 20}}
\put( 70,780){\line( 1, 0){180}}
\put( 70,760){\line( 1, 0){180}}
\put( 80,780){\line( 0,-1){ 20}}
\put(100,780){\line( 0,-1){ 20}}
\put(120,780){\line( 0,-1){ 20}}
\put(140,780){\line( 0,-1){ 20}}
\put(160,780){\line( 0,-1){ 20}}
\put(180,780){\line( 0,-1){ 20}}
\put(200,780){\line( 0,-1){ 20}}
\put(220,780){\line( 0,-1){ 20}}
\put(240,780){\line( 0,-1){ 20}}
\put(150,730){\vector( 0, 1){ 20}}
\put( 10,695){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{rule in \(P\):}}}
\put( 10,765){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{LBA:}}}
\put(415,690){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ 
  \(\tapetriple{\omittapeentry}{\omittapeentry}{p}
  \tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}
  \tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}\)}}}
\put(440,735){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{state \(p\)}}}
\put(160,735){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{state \(q\)}}}
\put(117,690){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ 
  \(\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}
  \tapetriple{\omittapeentry}{\omittapeentry}{q}
  \tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}\)}}}
\put(287,690){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{\small e.g., movement}}}
\put(287,672){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{\small to the left}}}
\put( 10,640){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{\(s\):}}}
\end{picture}}}
%
\afigcap{2}{Simulation in the first case (sketch)}
%
\end{figure*}
%
Thus, for \((p,y,R)\in\delta(q,x)\), the rules
%
\[\alpha\tapetriple{a}{x}{q}\tapetriple{b}{z}{\omittapeentry}\to
\alpha\tapetriple{a}{y}{\omittapeentry}\tapetriple{b}{z}{p}\]
for \(\alpha\in N^{j-1}\) (nonstate symbols only), \(a,b\in\Sigma\),
\(z\in\Gamma\) are in \(P\); for \((p,y,L)\in\delta(q,x)\) the rules
\ifx\customadjustc\undeftex\else\customadjustc\fi
%
\[\alpha\tapetriple{a}{z}{\omittapeentry}\tapetriple{b}{x}{q}\to
\alpha\tapetriple{a}{z}{p}\tapetriple{b}{y}{\omittapeentry}\]
%
for \(\alpha\in N^{j-2}\) (nonstate symbols only), \(a,b\in\Sigma\),
\(z\in\Gamma\) are in~\(P\)\@.
%
\apar{4-7}
Since the positions to the right and to the left of the ``valley
blip'' \(j\) are both valuated higher than the blip itself, these
rules become \(s\)-weakly growing with a symbol valuation according to
the conditions we stated above\@. To continue working, that is, to
apply such a rule on a sentential form, there must exist at least
\(j-1\) symbols in the sentential form to the left of the state\@.
%
\apar{4-8}
Therefore, at the left-hand border we condense several steps:
For \(w,w'\in\Sigma^{j-1}\), \(w=w_{1}\dots w_{j-1}\), 
\(w'=w_{1}'\dots w_{j-1}'\), \(x,y\in\Sigma\),\(q,p\in Q\) with
\(wqx\compsteps{M}w'yp\) the rules
%
\[\tapetriple{a_{1}}{w_{1}}{\leftendtape}
\tapetriple{a_{2}}{w_{2}}{\omittapeentry}\dots
\tapetriple{a_{j-1}}{w_{j-1}}{\omittapeentry}\tapetriple{a}{x}{q}
\tapetriple{b}{z}{\omittapeentry}\to
\tapetriple{a_{1}}{w_{1}'}{\leftendtape}
\tapetriple{a_{2}}{w_{2}'}{\omittapeentry}\dots
\tapetriple{a_{j-1}}{w_{j-1}'}{\omittapeentry}
\tapetriple{a}{y}{\omittapeentry}\tapetriple{b}{z}{p}\]
%
for \(a_{1}\dots a_{j-1},a,b\in\Sigma\), \(z\in\Gamma\) are in \(P\)\@.
(The \(\leftendtape\) here serves as a mark for the left-hand border\@.)
%
\apar{4-9}
To build an initial sentential form for the input 
\(a_{1}\dots a_{j}\dots a_{n}\), we use an analogous condensation of
steps: For \(q_{0}a_{1}\dots a_{j-1}\compsteps{M}a_{1}'\dots a_{j-1}'p_{0}\) 
we build 
%
\[
\tapetriple{a_{1}}{a_{1}'}{\leftendtape}
\tapetriple{a_{2}}{a_{2}'}{\omittapeentry}
\dots\tapetriple{a_{j-1}}{a_{j-1}'}{\omittapeentry}
\tapetriple{a_{j}}{a_{j}}{p_{0}} 
\tapetriple{a_{j+1}}{a_{j+1}}{\omittapeentry}\dots
\tapetriple{a_{n}}{a_{n}}{\rightendtape}
\]
%
(where \(\leftendtape\) serves to mark the left-hand, and
\(\rightendtape\) to mark the right-hand borders)\@.
%
\apar{4-10}
Triples containing an accepting state are transformed into their first
component, which then become terminal symbols\@. Every triple near a
terminal is transformed in this way, too\@. For a detailed and explicit
construction of the grammar see~\cite{cj96-04-22}\@.
%
\paragraph{For the second case (ii):}
%
\apar{4-11}
In the case of a ``peak blip'' we can use the same algorithm as we
used in the first case\@. In fact, we can use the same grammar\@. We
just have to redefine the symbol valuation so that the nonterminals
representing simple tape cells are valuated higher than the
nonterminals containing a state\@.
%
\paragraph{For the third case (iii):}
%
\apar{4-12}
Concerning a monotone increasing position valuation (up to the
position \(j+1\)), we relate the state with a greater value (than the
simple tape cells) for moving to the right and with a lower value for
moving to the left\@. To do this, we mark the state with the direction
it moved the last time\@. With a reversal (change of direction of the
move) this value must be changed\@. It is no problem in a weakly
growing grammar to change from a lower to a greater value\@. But going
the other way, we will use a trick to erase the ``surplus weight\@.''
First, it is encoded in a certain symbol (we will use a star
\(\tapereversemark\)) and laid down beside the point of reversal\@. From
there it is passed through to the right to be swallowed\@. This is
illustrated in Figure~3\@.
%
\begin{figure*}
\fbox{\parbox[t]{\textwidth}{%
%
\begin{center}
\setlength{\unitlength}{0.135ex}%
%
\begin{picture}(570,155)(20,650)
\thicklines
\put(420,780){\line( 1, 0){140}}
\put(420,760){\line( 1, 0){140}}
\put(430,780){\line( 0,-1){ 20}}
\put(450,780){\line( 0,-1){ 20}}
\put(470,780){\line( 0,-1){ 20}}
\put(490,780){\line( 0,-1){ 20}}
\put(510,780){\line( 0,-1){ 20}}
\put(530,780){\line( 0,-1){ 20}}
\put(550,780){\line( 0,-1){ 20}}
\put( 90,780){\line( 1, 0){140}}
\put( 90,760){\line( 1, 0){140}}
\put(100,780){\line( 0,-1){ 20}}
\put(120,780){\line( 0,-1){ 20}}
\put(140,780){\line( 0,-1){ 20}}
\put(160,780){\line( 0,-1){ 20}}
\put(180,780){\line( 0,-1){ 20}}
\put(200,780){\line( 0,-1){ 20}}
\put(220,780){\line( 0,-1){ 20}}
\put(170,730){\vector( 0, 1){ 20}}
\put(290,720){\vector( 1, 0){ 70}}
\put(135,740){\vector( 1, 0){ 25}}
\put(480,730){\vector( 0, 1){ 20}}
\put(470,740){\vector(-1, 0){ 25}}
\put( 20,770){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{LBA:}}}
\put(460,680){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ 
  \(\tapetriple{\omittapeentry}{\omittapeentry}{p^{L}}
    \tapetriple{\omittapeentry}{\omittapeentry}{\tapereversemark}\)}}}
\put(180,735){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{state \(q\)}}}
\put(135,680){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{ 
  \(\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}
    \tapetriple{\omittapeentry}{\omittapeentry}{q^{R}}\)}}}
\put(295,700){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{\small reversal}}}
\put(495,735){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{state \(p\)}}}
\put( 20,685){\makebox(0,0)[lb]{\raisebox{0ex}[0ex][0ex]{rule in \(P\):}}}
\end{picture}
\smallskip
In the sentential form, the following should happen:
\smallskip
%
\begin{align*}
%
 &
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}\dots
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}
\tapetriple{\omittapeentry}{\omittapeentry}{p^{L}}
\tapetriple{\omittapeentry}{\omittapeentry}{\tapereversemark} 
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}\dots
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}
\tapetriple{\omittapeentry}{\text{swallower}}{\omittapeentry}\\
%
\extendarrow{\text{ passing}} &
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}\dots
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}
\tapetriple{\omittapeentry}{\omittapeentry}{p^{L}}
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}\dots
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}
\tapetriple{\omittapeentry}{\omittapeentry}{\tapereversemark} 
\tapetriple{\omittapeentry}{\text{swallower}}{\omittapeentry}\\
%
\extendarrow{\text{ swallowing}} &
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}\dots
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}
\tapetriple{\omittapeentry}{\omittapeentry}{p^{L}}
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}\dots
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}
\tapetriple{\omittapeentry}{\omittapeentry}{\omittapeentry}
\tapetriple{\omittapeentry}{\text{swallower}}{\omittapeentry}
%
\end{align*}
\sentence
%
\end{center}}}
%
\afigcap{3}{Simulation with swallower}
%
\end{figure*}
%
It is no problem to let the ``surplus weight'' (encoded in the star
\(\tapereversemark\)) pass through to the right\@.
%
\apar{4-13}
We now introduce a swallower\@. Informally, a swallower consists of a
string \(\theta\) together with some rules that can be integrated into
a given \(s\)-weakly growing context-sensitive grammar \(G\) so that
every sentential form \(wY\theta\) can be transformed into
\(wX\theta\), where the nonterminal \(X\) is valuated lower than the
nonterminal \(Y\) by a symbol valuation for~\(G\)\@.
%
\begin{alabsubtext}{Definition}{6}{}
%
Let \(s\) be an unsteady position valuation which is monotone increasing 
on an initial part up to a position after its first blip, and
let \(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\)\@.
Define a swallower for \(s\) and \(G\) (also called an \emph{\(s\)-swallower 
for \(G\)}) to be a quintuple
\(\swallower{S}_{s,G}=\left(N_{1},N_{2},N_{\text{swallow}},
\theta,P_{\text{swallow}}\right)\) such that:
%
\begin{sloppypar}
\begin{itemize}
%
\item The components of the quintuple are
%
\begin{itemize}
%
\item \(N_{1}\) and \(N_{2}\) are nonempty subsets of \(N\), 
%
\item \(N_{\text{swallow}}\) is a set of nonterminals (not necessarily a
subset of \(N\)),
%
\item \(\theta\in N_{\text{swallow}}^{*}\) is a string, and
%
\item \(P_{\text{swallow}}\) is a set of rules of the form 
\(\alpha\to\beta\) where
\(\alpha,\beta\in\left(N\setunion N_{\text{swallow}}\setunion T\right)^{*}\)\@.
Every rule in \(P_{\text{swallow}}\) is context-sensitive\@.
%
\end{itemize}
\sentence
%
\item There exists a symbol valuation 
\(f\oftype\funcspace{N\setunion N_{\text{swallow}}\setunion T}{\universe{N}}\)
with
%
\begin{itemize}
%
\item \(f\) is a symbol valuation for \(G\), i.e., every rule in \(P\)
is \(s\)-weakly growing with~\(f\),
%
\item every rule in \(P_{\text{swallow}}\) is \(s\)-weakly growing
  with \(f\), and
%
\item for every \(X\in N_{1}, Y \in N_{2}\), it holds that \(f(X)<f(Y)\)\@.
%
\end{itemize}
\sentence
%
\item There exists an \(l\in\universe{N}\) such that for every 
\(w\in(N\setunion T)^{*}\) with \(\absvalue{w}\geq l\)
and for every \(X\in N_{1},Y\in N_{2}\), it holds that
\(wY\theta\multiderives{P_{\text{swallow}}}wX\theta\)\@.
%
\end{itemize}
\sentence
\end{sloppypar}
%
If \(N_{\text{swallow}}\subseteq N\) and
\(P_{\text{swallow}}\subseteq P\), we also call \(\counter{S}_{s, G}\) an
\(s\)-swallower \emph{in} \(G\)\@. If \(s\) and \(G\) are clear from the
context, the subscripts are dropped\@.
%
\end{alabsubtext}
%
\apar{4-14}
To illustrate how a swallower can be built, we give an example first\@.
%
\begin{alabsubtext}{Example}{3}{}
\exampfontshape
%
\apar{Example 3-1}
Take the unsteady position valuation \(\identfunc\) defined by
\(\identfunc(i)\equdef i\) for every \(i\in\universe{N}^{+}\)\@.
%
\apar{Example 3-2}
Let \(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{\identfunc}\)
with \(X,Y\in N\), and let \(f\) be a symbol valuation for \(G\) with
\(f(X)=1\), \({f(Y)=2}\)\@.
%
\apar{Example 3-3}
Define
\(\swallower{S}=
\left(N_{1},N_{2},N_{\text{swallow}},\theta,P_{\text{swallow}}\right)\)
with \(N_{1}\equdef \{X\}\), \(N_{2}\equdef\{Y\}\),
\(N_{\text{swallow}}\equdef\left\{M,[\tapereversemark],A,B,V\right\}\), 
\(\theta\equdef MAV\), and a set of rules
\(P_{\text{swallow}}\) comprising
%
\begin{alignat*}{6}
%
\rulename{(R1)} & \quad & YM &\to X[\tapereversemark] \qquad &
\rulename{(R2)} & \quad & [\tapereversemark]AV &\to MBA \qquad &
\rulename{(R3)} & \quad & BA &\to AV
%
\end{alignat*}
\sentence
%
Using these rules out of \(P_{\text{swallow}}\), the following derivation 
steps are possible:
%
\[YMAV\derives{R1}X[\tapereversemark]AV\derives{R2}XMBA\derives{R3}XMAV\]
\sentence
%
Now extend the symbol valuation \(f\) to \(N_{\text{swallow}}\) as follows:
%
\begin{alignat*}{3}
%
f(M) &\equdef 1 \qquad & f([\tapereversemark]) &\equdef 2 & & \\
f(A) &\equdef 1 \qquad & f(B) &\equdef 8 \qquad & f(V) &\equdef 5
%
\end{alignat*}
%
In this way we obtain the following valuations for the rules in 
\(P_{\text{swallow}}\):
%
\begin{alignat*}{4}
%
\text{for \(\rulename{(R1)}\):} & \quad &
1\mult 2+2\mult 1 &={} & 4 &<5 & &=1\mult 1+2\mult 2\\
%
\text{for \(\rulename{(R2)}\):} & \quad &
1\mult 2+2\mult 1+3\mult 5 &={} & 19 &<20 & &=1\mult 1+2\mult 8+3\mult 1\\
%
\text{for \(\rulename{(R3)}\):} & \quad &
1\mult 8+2\mult 1 &= & 10 &<11 & &={} 1\mult 1+2\mult 5
%
\end{alignat*}
\sentence
%
Thus, these rules are \(\identfunc\)-weakly growing with~\(f\)\@.
%
\apar{Example 3-4}
In the construction of these rules, we exploit that with the position
valuation \(\identfunc\), a value moving from the first to the second
position can be divided in half (this happens in \(\rulename{(R2)}\)
with the ``value'' 1 of the star), and moving from the third to the
second position it must be multiplied only with one and a half (this
happens in \(\rulename{(R2)}\) with the ``value'' \(f(V)-f(A)=4\))\@.
Here the values are chosen in a way that dividing the value collected
in \(B\) by 2 (that is
\(\ceiling{\frac{1}{2}\mult 1}+\frac{3}{2}\mult 4=7=f(B)-f(A)\)
and happens in \(\rulename{(R3)}\)) the situation of the beginning is
restored\@.
%
\apar{Example 3-5}
In this way, the sentential form \(MAV\) together with the set of
rules \(P_{\text{swallow}}\) swallows a value encoded in the star, and 
\(\counter{S}\) is an \(\identfunc\)-swallower in~\(G\)\@.
%
{\nopagebreakbeginpar\markendlst{Example 3}}
\end{alabsubtext}
%
\apar{4-15}
Now we turn to the construction of a swallower for each unsteady position 
valuation that is monotone increasing at least up to a position after its 
first blip\@.
%
\begin{alabsubtext}{Lemma}{3}{}
%
\apar{4-16}
Let \(s\) be an unsteady position valuation which is monotone increasing 
on a beginning part up to a position after the first blip, 
and let \(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\)\@.
Let \(f\) be a symbol valuation for \(G\) that valuates at least two 
symbols out of \(N\) differently\@. Then there exists an \(s\)-swallower
for~\(G\)\@.
%
\end{alabsubtext}
%
\apar{4-17}
Note that this lemma also means that concerning an unsteady position valuation,
a positive growth rate of a rule does not necessarily mean a positive 
growth rate of the corresponding derivation step\@.
%
\begin{alabsubtext}{Proof of Lemma}{3}{}
\prooffontshape
%
\apar{Proof of Lemma 3-1}
We just introduce the construction of the swallower and how the symbol 
valuation \(f\) can be extended to become an appropriate symbol 
valuation for the swallower
\(\swallower{S}=
\left(N_{1},N_{2},N_{\text{swallow}},\theta,P_{\text{swallow}}\right)\)
as well\@.
%
\apar{Proof of Lemma 3-2}
Let \(j\) be the first blip of \(s\)\@.
Let \(N_{1}\) and \(N_{2}\) be nonempty subsets of \(N\) with
\(f(X)<f(Y)\) for every \(X\in N_{1},Y\in N_{2}\)\@. Define
\(N_{\text{swallow}}\equdef\left\{ M,[\tapereversemark],A,B,V\right\}\),
\(\theta\equdef MAV\), let
%
\[
l\equdef\condval{%
  j-1 & \text{if }s(j-1)=s(j)\\
  j-2 & \text{if }s(j-1)<s(j) 
}
\]
%
and define \(P_{\text{swallow}}\) as follows:
%
\begin{align*}
%
R_{1} &\equdef
\setof{\alpha YM\to\alpha X[\tapereversemark]}%
{\alpha\in(N\setunion T)^{l}\text{, }Y\in N_{2},\text{, }X\in N_{1}}\\
%
R_{2} &\equdef\setof{\alpha[\tapereversemark]AV\to\alpha MBA}%
{\alpha\in(N\setunion T)^{j-2}}\\
%
R_{3} &\equdef\setof{\alpha BA\to\alpha AV}%
{\alpha\in(N\setunion T)^{j\propsub 3}\mult\{M,\emptystring\}\text{, }
\absvalue{\alpha}=j-2}\\
%
P_{\text{swallow}} &\equdef R_{1}\setunion R_{2}\setunion R_{3}
%
\end{align*}
\sentence
%
Note that the lengths of \(\alpha\) in \(R_{2}\) and \(R_{3}\) are different,
and that \(M\) appears in \(R_{3}\) iff \({j>2}\)\@.
%
\apar{Proof of Lemma 3-3}
Now we extend the symbol valuation \(f\) to \(N_{\text{swallow}}\) with values
in \(\universe{Q}\) as follows, where
\(\mu\equdef\max\setof{f(Y)-f(X)}{X\in N_{1}\text{, }{Y\in N_{2}}}\):
%
\begin{xxalignat}{3}
%
f(M) &\equdef 1 & f([\tapereversemark]) &\equdef 1+\mu & f(A) &\equdef 1\\
%
f(B) &\equdef\lefteqn{\frac{1}{s(j)^{2}-s(j-1)\mult s(j+1)}\mult
(s(j-1)\mult s(j)\mult\mu+s(j)+s(j+1))+1} & & & & \\
%
f(V) &\equdef\lefteqn{\frac{1}{s(j)^{2}-s(j-1)\mult s(j+1)}\mult
(\left(s(j-1)\right)^{2}\mult\mu+s(j-1)+s(j))+1}
%
\end{xxalignat}
\sentence
%
\apar{Proof of Lemma 3-4}
It can be checked arithmetically that the rules in
\(P_{\text{swallow}}\) all are \(s\)-weakly growing with \(f\)\@. (To
check \(R_{2}\) and \(R_{3}\), it is helpful first to compute
\(s(j)\mult f(B)-s(j+1)\mult f(V)\) and \(s(j) \mult f(V)-s(j-1)\mult
f(B)\), respectively\@.) As we have seen in Lemma~1,
\(f\) can be transformed into a symbol valuation with values
in~\(\universe{N}^{+}\)\@.
%
\apar{Proof of Lemma 3-5}
Thus \(f\) is now a symbol valuation for the swallower as well\@. Let
\(w\in (N\setunion T)^{*}\) with \(\absvalue{w}\geq l\), and let
\(X\in N_{1}\), \(Y\in N_{2}\)\@. With \(\theta=MAV\) the following
derivation steps are possible:
%
\[wY\theta=wYMAV\derives{R_{1}}wX[\tapereversemark]AV\derives{R_{2}}wXMBA
\derives{R_{3}}wXMAV=wX\theta\]
\sentence
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 3}}
\end{alabsubtext}
%
\apar{4-18}
So we can integrate a swallower into an \(s\)-weakly growing
context-sensitive grammar, where \(s\) is unsteady and monotone
increasing on a beginning part up to a position after the first blip
\(j\), that simulates a linear bounded automaton in the way we
mentioned at the beginning of this section\@. To get a sentential form
that is not too long, we condense every two cells of the linear
bounded automaton (see linear tape compression in the literature)\@.
%
\apar{4-19}
When the linear bounded automaton accepts, the sentential form is
transformed into terminals and expanded at the same time\@. Together
with the expansion the swallower disappears\@. If \(s\) on a beginning
part is constant, we have the same conditions for border-handling
during the simulation as we had in the first and the second cases\@.
%
\paragraph{For the fourth case (iv):}
%
\apar{4-20}
Concerning an unsteady position valuation that is monotone decreasing
on a beginning part up to a position after the first blip \(j\), the
simulation of a linear bounded automaton works quite analogously\@. For
a move to the right, the state is related to a lower value, for a move
to the left the state is related to a higher value than the simple
tape cells\@. This means the ``surplus weight'' is generated in a
left-right reversal, and is passed through to the left, where it is
swallowed\@. The swallower is also constructed in a similar way: The
string and the parts of the rules that change are transposed, a dummy
symbol is added to the left-hand context of the rules in \(R_{3}\),
and the left-hand context of every rule is replaced by dummy
symbols\@. Such a swallower can be integrated in an analogous way to the
one introduced above, and thus the claim can be shown for this case,
too\@.
%
\paragraph{Conclusion:}
%
\apar{4-21}
Since in all cases (i) through (iv) we can construct an appropriate
weakly growing context-sensitive grammar, we have the following:
%
\begin{alabsubtext}{Theorem}{5}{}
%
For every unsteady position valuation \(s\), it holds that
\[\classoflang{WGCSL}_{s}=\classoflang{CSL}\]
\sentence
%
\end{alabsubtext}
\sentence
%
\apar{4-22}
For a more detailed description, see~\cite{cj96-04-22}\@.
%
\asection{5}{The Steady Position Valuation}
%
\apar{5-1}
We intend to find a characterization of a weakly growing
context-sensitive language class related to a steady position
valuation by linear bounded automata with a certain time bound\@. We
approach this goal in three steps: First, we estimate the length of a
derivation in a given weakly growing context-sensitive grammar related
to a steady position valuation, and realize an efficient simulation
(Section~5.1)\@. Second, we introduce an instrument that will help in
the simulation of linear bounded automata by weakly growing
context-sensitive grammars related to a steady position
valuation\@. This instrument is a new kind of counter: grammars that
count, where the counted items in fact are weight pieces
(Section~5.2)\@. With these preparations the simulation will be done
easily (Section~5.3)\@. Note, however, that with our methods it is not
possible to show a one-to-one correspondence, due to the counter's
capacity\@.
%
\asubsection{5.1}{Efficient Simulation of a Grammar}
%
\asubsubsection{5.1.1}{Connected Grammars}
%
\apar{5.1.1-1}
In a simulation of a grammar with a linear bounded automaton, the
automaton can follow the derivation step by step, if it is connected
(see Definition~7), while in a nonconnected grammar, in
every step it must move to the position of replacement first\@. To gain
an effective simulation, we will make use of the property to be
connected (see \cite{cj96-04-15}, \cite{cj96-04-01},~\cite{cj96-04-05})\@.
%
\begin{alabsubtext}{Definition}{7}{}
%
Let \(G=\langle N,T,S,P\rangle\) be a grammar\@. Let
\(w_{0}=S\derives{}w_{1}\derives{}\dots\derives{}w_{t}\) be a
derivation in \(G\), and let \((\alpha_{i}\to\beta_{i})\in P\) be the
rule applied in the step \(w_{i}\derives{}w_{i+1}\)\@. The derivation is
\emph{connected} if for each \(i=1,2,\dots,t-1\) the substrings
\(\alpha_{i}\) and \(\beta_{i-1}\) of \(w_{i}\) have a nonempty
overlap\@. The grammar \(G\) is connected if each derivation
\(w_{0}\multiderives{}w_{t}\) with \(w_{0}=S\) is connected\@.
%
\end{alabsubtext}
%
\apar{5.1.1-2}
Gladkii showed that every grammar (of both general and
context-sensitive types) can be transformed into an equivalent grammar
of the same type that is connected \cite{cj96-04-15}\@. Using Book's
proof in \cite{cj96-04-01}, in \cite{cj96-04-05} it was shown that
this also is true for quasi-growing context-sensitive grammars\@. Here
we will show that the same is true for \(s\)-weakly growing
context-sensitive grammars, for every steady position valuation~\(s\)\@.
%
\apar{5.1.1-3}
Book's proof carries over easily when we use Cremers normal form
(Theorem~3), and we can assume that the position valuation is monotone
increasing (see Theorem~4)\@.
%
\begin{alabsubtext}{Lemma}{4}{}
% 
Let \(s\) be a steady, strictly monotone increasing position valuation\@. 
Then for each grammar \(G \in \classofgrammar{WGCSG}_{s}\) in
Cremers normal form, there exists a connected grammar
\(G'\in WGCSG_{s}\) with
\(\gramtolang(G')=\gramtolang(G)\)\@. Additionally, the length of a
derivation for a word \(w\) in \(G'\) is at most doubled compared to
the length in~\(G\)\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{4}{}
\prooffontshape
%
\apar{Proof of Lemma 4-1}
Let \(G =\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\) in
Cremers normal form\@. Let \(f\) be a symbol valuation for~\(G\)\@.
%
\apar{Proof of Lemma 4-2}
Define a grammar \(G'=\langle N',T,\hat{S},P'\rangle\) by
\(N'\equdef N\setunion\setof{\hat{A}}{A\in N}\), that is, the old set of
nonterminals together with a set of new nonterminals in one-to-one
correspondence with the old, and the following rules:
%
\begin{align*}
%
P_{1}
  &\equdef\setof{\hat{A}B\to\hat{C}D,A\hat{B}\to\hat{C}D,A\hat{B}\to C\hat{D}}%
  {A,B,C,D\in N,(AB\to CD)\in P}\\
%
P_{2} &\equdef\setof{\hat{A}\to\hat{C}D,\hat{A}\to C\hat{D}}%
  {A,C,D\in N,(A\to CD)\in P}\\
%
P_{3} &\equdef\setof{\hat{A}\to a,\hat{A}X\to a\hat{X}}%
{A,X\in N,a\in T,(A\to a)\in P}\\
%
P_{4} &\equdef\setof{\hat{A}B\to A\hat{B}}{A,B\in N}\\
%
P' &\equdef P_{1}\setunion P_{2}\setunion P_{3}\setunion P_{4}
%
\end{align*}
\sentence
%
Following an argument given in \cite{cj96-04-01} we see that
\(\gramtolang(G')=\gramtolang(G)\), and \(G'\) is a connected
context-sensitive grammar\@. Now define a symbol valuation
\(f'\oftype\funcspace{N'\setunion T}{\universe{N}}\) for \(G'\)~by:
%
\begin{alignat*}{2}
%
f'(A) &\equdef s(2)^{2}\mult f(A) \quad & &\text{for every }A\in N\\
%
f'(\hat{A}) &\equdef s(2)^{2}\mult f(A)+s(2) \quad & &\text{for every }A\in N\\
%
f'(a) &\equdef s(2)^{2}\mult f(a) \quad & &\text{for every }a\in T
%
\end{alignat*}
\sentence
%
Then every production in \(P'\) is \(s\)-weakly growing with \(f'\) as
shown below\@.
%
\apar{Proof of Lemma 4-3}
Each rule from \(P\) grows at least by one with respect to \(f\)\@. The
factor \(s(2)^{2}\) in the definition of \(f'\) causes this growth
rate to rise to \(s(2)^{2}\)\@. As \(0<s(2)\leq s(1)\mult
s(2)<s(2)^{2}\) (because \(s(1)\geq 1\) and \(s\) is strictly monotone
increasing), the claim can be concluded for every rule of \(P'\)\@. To
illustrate, we take a closer look at the second rule in \(P_{1}\)\@.
Because \(AB\to CD\) is \(s\)-weakly growing with \(f\), the following
applies:
%
\[s(1)\mult f(A)+s(2)\mult f(B)+1\leq s(1)\mult f(C)+s(2)\mult f(D)\]
so
\[s(1)\mult s(2)^{2}\mult f(A)+s(2)^{3}\mult f(B)+s(2)^{2}\leq
s(1)\mult s(2)^{2}\mult f(C)+s(2)^{3}\mult f(D)\]
\sentence
%
Thus, for the new rule \(A\hat{B}\to\hat{C}D\), it holds that
%
\begin{align*}
%
s(1)\mult f'(A)+s(2)\mult f'(\hat{B}) &=s(1) \mult s(2)^{2}\mult f(A)
+s(2)\mult s(2)^{2}\mult f(B)+s(2)\mult s(2)\\
%
&\leq s(1)\mult s(2)^{2}\mult f(C)+s(2)\mult s(2)^{2}\mult f(D)\\
%
&<s(1)\mult s(2)^{2}\mult f(C)+s(1)\mult s(2)+s(2)\mult s(2)^{2}\mult f(D)\\
%
&=s(1)\mult f'(\hat{C})+s(2)\mult f'(D)
%
\end{align*}
\sentence
%
Thus we have \(G'\in\classofgrammar{WGCSG}_{s}\)\@. The second claim is
true following~\cite{cj96-04-01}\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 4}}
\end{alabsubtext}
%
\apar{5.1.1-4}
It is possible to use the same idea for other position valuations\@. We
even have connectivity if there is no known transformation into
Cremers normal form\@.
%
\asubsubsection{5.1.2}{Efficient Simulation}
%
\apar{5.1.2-1}
When we simulate a derivation with a weakly growing context-sensitive
grammar related to a steady position valuation by a linear bounded
automaton, we use the algorithm of Section~4 and Lemma~4\@. To
estimate the time bound for the linear bounded automaton, we estimate
the length of the derivation in the weakly growing context-sensitive
grammar related to the steady monotone increasing position valuation
by the value of the derived word\@. This is done by the natural
infinite extension of the position valuation\@. Such an extension
allows us to valuate arbitrarily long sentential forms\@. With every
application of a rule, the value of the sentential form increases (at
least by~one)\@.
%
\begin{alabsubtext}{Lemma}{5}{}
%
Let \(s\) be an infinite steady monotone increasing position
valuation\@. Let \(G=\langle N,T,S,P\rangle\) be an \(s\)-weakly
growing context-sensitive grammar, let \(u=u_{1}\dots u_{r}\),
\(v=v_{1}\dots v_{s}\in(N\setunion T)^{*}\) be sentential forms with
\(u\derives{}v\), and let
\(f\oftype\funcspace{N\setunion T}{\universe{N}^{+}}\) be a symbol
valuation for \(G\)\@. Then the following applies:
%
\[\sum_{i=1}^{r}s(i)\mult f(u_{i})+1\leq\sum_{i=1}^{s}s(i)\mult f(v_{i})\]
\sentence
%
That is, concerning steady position valuations, the positive growth
rate of a rule induces a positive growth rate of the corresponding 
derivation step\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{5}{}
\prooffontshape
%
Let \((\alpha\to\beta)\in P\) be the rule used in the derivation step
\(u\derives{}v\)\@. The growth rate of that rule is at least 1; we
denote it by \(g\)\@. Let us now valuate the whole sentential forms
\(u=u_{1}\alpha u_{2}\) and \(v=u_{1}\beta u_{2}\), and look at the
growth rate of the derivation step \(u\derives{G}v\)\@. We obtain the
value \(g\mult\growthfactor{w}(s)^{\absvalue{u_{1}}}\) where
\(\growthfactor{w}(s)^{|u_{1}|}\geq 1\), if \(r\) is length-preserving, 
and \(g\mult\growthfactor{w}(s)^{|u_{1}|}+b\) where, additionally, \(b>0\),
if it is length-increasing\@. As there are no length-decreasing rules,
this implies the claim\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 5}}
\end{alabsubtext}
%
\apar{5.1.2-2}
As we saw in Section~4 in the construction of swallowers, in the case
of an unsteady position valuation it is not possible to build a
natural extension such that the value of a sentential form increases
with every application of a weakly growing rule (see Lemma~3)\@. On
the other hand, because of this effect there cannot exist a swallower
for a steady position valuation\@. Thus we can estimate the length of
a derivation generating a word \(w\) in a grammar \(G\) by the
valuation of the word \(w\) itself\@.
%
\apar{5.1.2-3}
We conclude from Lemma~5 and Definition~3:
%
\begin{alabsubtext}{Lemma}{6}{}
%
Let \(s\) be an infinite steady strictly monotone increasing position
valuation\@. Let \(G=\langle N,T,S,P\rangle\in WGCSG_{s}\), let \(f\)
be an appropriate symbol valuation for \(G\)\@. Let
\(c=\max\setof{f(A)}{A\in N\setunion T}\)\@. Let
\(v\in\gramtolang(G)\)\@. Then the length of a derivation
\(S\multiderives{}v\) is not greater than
%
\[\sum_{i=1}^{\absvalue{v}}s(i)\mult c=
c\mult\sum_{i=1}^{\absvalue{v}}s(1)\mult\growthfactor{w}(s)^{i-1}\leq
\growthfactor{w}(s)^{\absvalue{v}}\mult\frac{c\mult
s(1)}{\growthfactor{w}(s)-1}\]
\sentence
%
\end{alabsubtext}
%
\apar{5.1.2-4}
Now we can estimate the computation time a linear bounded automaton
needs to simulate a weakly growing context-sensitive grammar related
to a steady position valuation using Theorem~4, Lemma~4, and
Lemma~6\@. (Here, \(\complexityclass{\(T\)-NSPACE-TIME}(s,t)\) denotes
the class of languages that are accepted by a one-tape
nondeterministic Turing machine with the given space bound \(s\) and
the given time bound \(t\); see~\cite{cj96-04-34}\@.)
%
\begin{alabsubtext}{Theorem}{6}{}
%
Let \(s\) be a steady nonconstant position valuation\@.
Let \(\growthfactor{w}=
\max\{\growthfactor{w}(s),\frac{1}{\growthfactor{w}(s)}\}\)\@. Then:
%
\[\classoflang{WGCSL}_{s}\subseteq
\complexityclass{\(T\)-NSPACE-TIME}\left(n,\orderof{\growthfactor{w}^{n}}\right)\]
\sentence
%
\end{alabsubtext}
%
\asubsection{5.2}{Counters}
%
\apar{5.2-1}
We will introduce a counter as an instrument to lay down encoded
weight pieces, consisting of a string and some rules\@. We will use it
in a simulation of a linear bounded automaton by a weakly growing
context-sensitive grammar\@. The capacity of the counter used will cause
a bound on the number of steps that can be simulated\@.
%
\begin{alabsubtext}{Definition}{8}{}
%
\apar{Definition 8-1}
Let \(s\) be a steady strictly monotone increasing position valuation,
and let \(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\)\@.
Define a \emph{counter for \(G\) related to the position valuation
\(s\)}, also called an \emph{\(s\)-counter for \(G\)}, to be a
quintuple \(\counter{Z}_{s,G}= 
(N_{1},N_{2},N_{\text{count}},(z_{n})_{n\in\universe{N}^{+}},
P_{\text{count}})\),
such that:
%
\begin{itemize}
%
\item The components of the quintuple are
%
\begin{itemize}
%
\item \(N_{1}\) and \(N_{2}\) are nonempty subsets of \(N\),
%
\item \(N_{\text{count}}\) is a set of nonterminals (not necessarily a
subset of \(N\)),
%
\item \((z_{n})_{n\in\universe{N}^{+}}\) is a sequence of start strings 
with \(z_{n}\in N_{\text{count}}^{n}\) for every
\(n\in\universe{N}^{+}\), and
%
\item \(P_{\text{count}}\) is a finite subset of 
\((N_{2}\catlang N_{\text{count}}^{*}\times N_{1}\mult
N_{\text{count}}^{*})\setunion
(N_{\text{count}}^{*}\times N_{\text{count}}^{*})\);
every rule in \(P_{\text{count}}\) is length-preserving\@.
%
\end{itemize}
\sentence
%
\item There exists a symbol valuation 
\(f\oftype\funcspace{N\setunion N_{\text{count}}\setunion T}{\universe{N}}\)
where
%
\begin{itemize}
%
\item \(f\) is a symbol valuation for \(G\), i.e., every rule in \(P\)
is \(s\)-weakly growing with \(f\),
%
\item every rule in \(P_{\text{count}}\) is \(s\)-weakly growing with
\(f\), and
%
\item for every \(X\in N_{1},Y\in N_{2}\), it holds that \(f(X)<f(Y)\)\@.
%
\end{itemize}
\sentence
%
We say that \(\restrfun{f}{N_{1}\setunion N_{2}\setunion N_{\text{count}}}\)
is a \emph{symbol valuation for} \(\counter{Z}\)\@.
%
\end{itemize}
\sentence
%
\apar{Definition 8-2}
If \(N_{\text{count}}\subseteq N\) and \(P_{\text{count}}\subseteq P\),
we also call \(\counter{Z}_{s, G}\) an \(s\)-counter \emph{in} \(G\)\@.
If \(s\) and \(G\) are clear from the context, the subscripts are
dropped\@.
%
\end{alabsubtext}
%
\apar{5.2-2}
For every \(X\in N_{1}\) and \(Y\in N_{2}\), the counter counts the
weight piece \(f(Y)-f(X)\) by applying an appropriate rule out of
\(N_{2}\mult N_{\text{count}}^{*}\times N_{1}\mult N_{\text{count}}^{*}\) 
(and after that possibly some rules out of
\(N_{\text{count}}^{*}\times N_{\text{count}}^{*}\)) on the string
\(Y z_{n}\), where \(z_{n}\) is one of the start strings of
\(\counter{Z}\)\@. This results in a string \(Xz_{n}'\) of the same
length\@. Another weight can be counted applying rules as mentioned
above on \(Yz_{n}'\), and so on\@. To use the counter to count several
amounts of weight, we apply corresponding increment rules (which are
not in \(P_{\text{count}}\), but will be added to \(P\) in order to
use the counter in \(G\))\@.
%
\begin{alabsubtext}{Definition}{9}{}
%
\apar{Definition 9-1}
Let \(s\) be a steady strictly monotone increasing position valuation,
let \(G\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\)\@. Let
\(\counter{Z}\) be an \(s\)-counter for \(G\), and let \(f\) be a
symbol valuation for \(G\) and for~\(\counter{Z}\)\@.
%
\apar{Definition 9-2}
The set \(\rho(\counter{Z},f)\) of \emph{increment rules for
\(\counter{Z}\) with \(f\)} is defined by:
%
\[\rho(\counter{Z},f)\equdef
\setof{(X\to Y)}%
{X\in N_{1}\text{, }Y\in N_{1}\setunion N_{2}\text{, and }f(X)<f(Y)}\]
\sentence
%
\end{alabsubtext}
%
\apar{5.2-3}
Consider a derivation starting with a string of the form \(Xz_{n}\),
where \(X\in N_{1}\) and \(z_{n}\) is the start string with index (and
length) \(n\)\@. We are interested in the number of times an increment
rule can be used (and the weight piece generated by it can be handled)
in such a derivation\@. So, we define the \emph{capacity}
\(K_{\counter{Z}}(n)\) to be the maximum number of times that it is
possible to have an occurrence of an increment rule in a derivation
starting with \(Xz_{n}\) and ending with \(X'\tilde{z}\), where
\(X'\in N_{1}\) and \(\strlength{\tilde{z}}=\strlength{z_{n}}\)\@. Note
that there are two kinds of increment rules\@. The first kind (which we
call a ``collecting weights'' rule) leaves the first symbol in
\(N_{1}\)\@. The second kind of increment rule (which replaces the first
symbol from one in \(N_{1}\) to one in \(N_{2}\)) is the kind of
increment rule that directly influences the counter\@.
%
\begin{alabsubtext}{Definition}{10}{}
%
Let \(s\) be a steady strictly monotone increasing position valuation,
let \(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\),
let \(\counter{Z}\) be an \(s\)-counter for \(G\), let \(z_{n}\) be
the start string with index \(n\), and let \(V_{\counter{Z},G}\) be
the set of all symbol valuations for \(\counter{Z}\) and \(G\)\@. The
capacity function
\(K_{\counter{Z}}\oftype\funcspace{\universe{N}^{+}}{\universe{N}^{+}}\)
of \(\counter{Z}\) is defined as follows:
%
\[
K_\counter{Z}(n)\equdef\max\setof{\setsize{\setof{j}{r_{j}\in\rho(\counter{Z},f)}}}
%
{\begin{aligned}
%
&f\in V_{\counter{Z},G}\text{, }X,X'\in N_{1}\text{, }
\tilde{z}\in N_{\text{count}}^{n}\text{, }k\in\universe{N}\text{,}\\
%
&(r_{1},\dots,r_{k})\in\left(P_{\text{count}}\setunion
\rho(\counter{Z},f)\right)^{k}\text{,}\\
%
&Xz_{n}\derives{r_{1}}\dots\derives{r_{k}}X'\tilde{z}
%
\end{aligned}}
%
\]
\sentence
%
\end{alabsubtext}
%
Because the set \(N\) is finite and each of the rules is
length-preserving, the capacity of a counter certainly is well
defined\@. Because of the possibility of collecting weights (in fact,
we only need to extend \(N_{1}\) to raise the capacity of a counter by
a constant factor), there is for every counter \(\counter{Z}\) and
every \(c\in\universe{N}^{+}\) a counter \(\counter{Z'}\) with
\(K_{\counter{Z'}}={c\mult K_{\counter{Z}}}\)\@.
%
\apar{5.2-4}
Let us now have a look at a specific counter to see how it works\@.
%
\begin{alabsubtext}{Example}{4}{}
\exampfontshape
%
\apar{Example 4-1}
Let \(s\) be a steady strictly monotone increasing position valuation\@.
Let \(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\) with 
\(\{\#,M\}\subseteq N\)\@. Define \(\counter{Z}=(N_{1},N_{2},N_{\text{count}},
(z_{n})_{n\in\universe{N}^{+}},P_{\text{count}})\) by:
\(N_{1}\equdef\{M\}\), \(N_{2}\equdef\{ \#\}\),
\(N_{\text{count}}\equdef\left\{[0],[1],\dots,[k]\right\}\)
for a \(k\in\universe{N}^{+}\),
\(z_{n}\equdef[0]^{n}\) for each \(n\in\universe{N}^{+}\), and
\(P_{\text{count}}\) consisting of the rules:
%
\[
%
\begin{alignedat}{2}
%
\rulename{(R1)} &\quad & \#[i] &\to M[i+1]\\
%
\rulename{(R2)} &\quad & [i+1][i] &\to [i][i+1]
%
\end{alignedat}
%
\qquad\text{ for }i=0,\dots,k-1
%
\]
\sentence
%
The symbol valuation \(f\) defined by
%
\[f(M)\equdef 1\text{, }f(\#)\equdef 2\text{, }f([i])\equdef i+1\text{ for }i=0,\dots,k\]
%
shows that \(\counter{Z}\) is an \(s\)-counter for \(G\)\@. \(M\to\#\)
is the only possible increment rule, thus the capacity is
\(K_\counter{Z}(n)=k\mult n\)\@.
%
\apar{Example 4-2}
If we change rule (R2) to
%
\[
%
\begin{alignedat}{2}
%
\rulename{(R2\primerulemark)} &\quad & [i+1][i] &\to [0][i+1]
%
\end{alignedat}
%
\qquad\text{ for }i=0,\dots,k-1
%
\]
%
we obtain a counter with polynomial capacity\@. (In the symbol
valuation define \(f([i])\equdef\growthfactor{w}(s)^{i}\) for
\(i=0,\dots,k\)\@.)
%
{\nopagebreakbeginpar\markendlst{Example 4}}
\end{alabsubtext}
%
\apar{5.2-5}
We have seen counters with linear and with polynomial capacities\@.
What about exponential capacity\@? As we reach for an inversion of
Theorem~6, this is our goal\@.
%
\apar{5.2-6}
Let us check the possible capacity for a counter that follows the algorithm
``treat the string as a number to a certain base, and add up
arithmetically\@.'' We look at an example first\@.
%
\begin{alabsubtext}{Example}{5}{}
\exampfontshape
%
\apar{Example 5-1}
Let \(s_{2}\) be the position valuation defined by
\(s_{2}(i)\equdef 2^{i-1}\) for every \(i\in\universe{N}^{+}\)\@. Let
\(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s_{2}}\) with
\(\{\#,M\}\subseteq N\)\@. Define \(\counter{Z}=
\left(N_{1},N_{2},N_{\text{count}},(z_{n})_{n\in\universe{N}^{+}},
P_{\text{count}}\right)\) by \(N_{1}\equdef\{M\}\), \(N_{2}\equdef\{\#\}\),
\(N_{\text{count}}\equdef\left\{[0],[1],[U]\right\}\), 
\(z_{n}\equdef[0]^{n}\text{ for each }n\in\universe{N}^{+}\)
and \(P_{\text{count}}\) consisting of the rules:
%
\begin{alignat*}{4}
%
\rulename{(R1)} &\quad & \#[0] &\to M[1] &\qquad
\rulename{(R3)} &\quad & [U][0] &\to [0][1]\\
%
\rulename{(R2)} &\quad & \#[1] &\to M[U] &\qquad
\rulename{(R4)} &\quad & [U][1] &\to [0][U]
%
\end{alignat*}
\sentence
%
Using rules \(\rulename{(R1)}\)--\(\rulename{(R4)}\) above, together
with the rule \(M\to\#\), for every start string \(z_{n}\) the
following derivation steps are possible in \(\counter{Z}\):
%
\begin{equation*}
\begin{split}
%
Mz_{n}={} &M[0][0][0]\dots[0]\multiderives{}M[1][0][0]\dots[0]
  \multiderives{}M[U][0][0]\dots[0]\\
%
\multiderives{}{} &M[0][1][0]\dots[0]\multiderives{}M[1][1][0]\dots[0]
  \multiderives{}M[U][1][0]\dots[0]\\
%
\multiderives{}{} &M[0][U][0]\dots[0]\multiderives{}M[0][0][1][0]\dots[0]\\
%
\multiderives{}{} &\dots\multiderives{}M[U][U]\dots[U]
%
\end{split}
\end{equation*}
\sentence
%
At first glance, this looks like an \(s_{2}\)-counter with capacity
%
\[2\mult\sum_{i=1}^{n}2^{i-1}=\sum_{i=1}^{n}2^{i}=2^{n+1}-2\geq 2^{n}\]
\sentence
%
Now let
\(f\oftype
\funcspace{N_{1}\setunion N_{2}\setunion N_{\text{count}}}{\universe{N}}\)
be a symbol valuation\@. Then we have:
%
\begin{description}
%
\item[For \(\rulename{(R3)}\):]
%
\begin{align*}
%
1\mult f([U])+2\mult f([0]) &<1\mult f([0])+2\mult f([1])\\
%
\text{which implies }f([U])-f([1]) &<f([1])-f([0])
%
\end{align*}
%
\item[For \(\rulename{(R4)}\):]
%
\begin{align*}
%
1\mult f([U])+2\mult f([1]) &<1\mult f([0])+2\mult f([U])\\
%
\text{which implies }f([1])-f([0]) &<f([U])-f([1])
%
\end{align*}
%
\end{description}
\sentence
%
\apar{Example 5-2}
Both of these inequalities cannot be fulfilled at the same
time\@. Thus there exists no symbol valuation with which all rules of
\(P_{\text{count}}\) are \(s_{2}\)-weakly growing\@. This implies that
\(\counter{Z}\) is not an \(s_{2}\)-counter, for every
\(G\in\classofgrammar{WGCSG}_{s_{2}}\)\@.
%
{\nopagebreakbeginpar\markendlst{Example 5}}
\end{alabsubtext}
%
\apar{5.2-7}
The reason is, that in every rule we transport a portion of the weight
piece plus an increment for making the rule weakly growing to the
right\@. When all these portions and increments come together, they
add up to a value that must not exceed the original weight piece,
because this sum is to be handled in the same way, arbitrarily
often\@.
%
\apar{5.2-8}
We will now look at the upper bound for the capacity of a counter
\(\counter{Z}_{s, G}\) which works after the following mechanism:
It treats the start string as a number (where each digit of that
number is represented by several symbols (bits) of the string) and
increments this encoded number arithmetically\@. We fix the number of
symbols used to represent a digit by \(l\in\universe{N}\)\@. How many
different digits \([0],[1],\dots,[i_{\max}]\) can now be represented
by \(l\) bits of the string without violating the property of
\(\counter{Z}_{s,G}\) to be an \(s\)-counter\@? We have seen in
Example~5 that, e.g., for \(l=1\) to choose \(i_{\max}=1\) (that is,
choosing the base of the number representation to be \(2\)) violates
this property\@.
%
\apar{5.2-9}
This number of digits representable by \(l\) bits while respecting the
\(s\)-counter property determines the base of the number representation
that we use to count weight pieces\@. Thus, it also determines the
maximal capacity reachable by such a counter\@.
%
\apar{5.2-10}
In the following lemma, \([0],[1],\dots,[i_{\max}]\), and \([U]\) are
metasymbols, each standing for \(l\) letters (bits) that encode the
digits \(0,1,\dots,i_{\max}\) of the number representation, and the
\(l\) letters of \([U]\) represent the overflow, which contains \(0\)
and a carry for the next position\@.
%
\begin{alabsubtext}{Lemma}{7}{}
%
\apar{Lemma 7-1}
Let \(s\) be an infinite steady strictly monotone increasing position
valuation\@. Let
\(G=\langle N,T,S,P\rangle\in\classofgrammar{WGCSG}_{s}\) with 
\(\{\#,M\}\subseteq N\), and let \(\counter{Z}=
\left(N_{1},N_{2},N_{\text{count}},(z_{n})_{n\in\universe{N}^{+}},
P_{\text{count}}\right)\) be a counter with \(M\in N_{1}\),
\(\#\in N_{2}\)\@. Let \(l\in\universe{N}^{+}\)\@.
%
\apar{Lemma 7-2}
If \(\counter{Z}_{s,G}\) works after the following scheme (where
\([0],[1],\dots,[i_{\max}],[U]\in N_{\text{count}}^{l}\),
\(i_{\max}\in\universe{N}\), \(i=0,\dots,i_{\max}-1\)):
%
\begin{alignat*}{4}
%
\rulename{(R1)} &\quad & \#[i] &\to M[i+1] & \qquad
\rulename{(R3)} &\quad & [U][i] &\to [0][i+1]\\
%
\rulename{(R2)} &\quad & \#[i_{\max}] &\to M[U] & \qquad
\rulename{(R4)} &\quad & [U][i_{\max}] &\to [0][U]
%
\end{alignat*}
%
and if \(\counter{Z}_{s,G}\) is an \(s\)-counter, then the capacity
of the counter \(\counter{Z}_{s,G}\) is bounded~by
%
\[K_\counter{Z}(n)\leq(c+2)\mult
\ceiling{\growthfactor{w}(s)^{l}-1}^{\floor{\frac{n}{l}}}\]
%
where \(c\) is a constant depending on \(\counter{Z}_{s,G}\)\@.
%
\end{alabsubtext}
%
\apar{5.2-11}
Note that for \(\growthfactor{w}(s)^{l}\leq 2\) the capacity is at
most linear, but for \(\growthfactor{w}(s)^{l}>2\) it is at most
exponential\@. As we stated above, the goal of this lemma is to
estimate~\(i_{\max}\)\@.
%
\begin{alabsubtext}{Proof of Lemma}{7}{}
\prooffontshape
%
\apar{Proof of Lemma 7-1}
Let \(f\) be a symbol valuation for \(\counter{Z}\)\@. 
Define a function
\(g\oftype\funcspace{N_{\text{count}}^{l}}{\universe{N}^{+}}\) by 
\(g(a_{1}\dots a_{l})\equdef\sum\limits_{i=1}^{l}s(i)\mult f(a_{i})\), 
where \(a_{1},\dots,a_{l}\in N_{\text{count}}\)\@. That is, \(g\)
valuates the metasymbols \([0],[1],\dots,[i_{\max}], [U]\), each
represented by \(l\) letters out of \(N_{\text{count}}\), by
condensing the symbol and the position valuation\@. Let
\(\growthfactor{w}\) denote the growth factor
\(\growthfactor{w}(s)\)\@. Then we have\@:
%
\paragraph{For \protect\(\protect\rulename{(R3)}\protect\):}
%
\apar{Proof of Lemma 7-2}
\[g([U])-g([0])<\growthfactor{w}^{l}\mult\left(g([i+1])-g([i])\right)
\text{ for }i=0,\dots,i_{\max}-1\]
%
\paragraph{For \protect\(\protect\rulename{(R4)}\protect\):}
%
\apar{Proof of Lemma 7-3}
\[g([U])-g([0])<\growthfactor{w}^{l}\mult\left(g([U])-g([i_{\max}])\right)\]
%
Let \(\mu=g([U])-g([0])\)\@. This implies
%
\begin{align*}
%
\mu\equdef{}
  &g([U])+(-g([i_{\max}])+g([i_{\max}]))+\dots
  +(-g([1])+g([1]))-g([0])\\
%
 ={} &(g([U])-g([i_{\max}]))+(g([i_{\max}])-g([i_{\max}-1]))+\dots
  +(g([1])-g([0]))\\
%
 >{} &\underbrace{\frac{1}{\growthfactor{w}^{l}}\mult\mu+
  \frac{1}{\growthfactor{w}^{l}}\mult\mu+\dots+
  \frac{1}{\growthfactor{w}^{l}}\mult\mu}_{i_{\max}+1\text{ times}}\\
%
 ={} &\frac{i_{\max}+1}{\growthfactor{w}^{l}}\mult\mu
%
\end{align*}
\sentence
%
For \(\rulename{(R1)}\) and \(\rulename{(R2)}\), \(\mu>0\), so
\(i_{\max}+1<\growthfactor{w}^{l}\), from which it follows that 
\(i_{\max}=\ceiling{\growthfactor{w}^{l}-2}\) (which means \(i_{\max}=0\) for
\(\growthfactor{w}^{l}\leq 2\))\@. Thus, we have a number representation
to the base \(\ceiling{\growthfactor{w}^{l}-1}\)\@.
%
\apar{Proof of Lemma 7-4}
Starting with \(M[0]^{\floor{\frac{n}{l}}}\alpha\), where
\(\alpha\in N_{\text{count}}^{*}\) with
\(\absvalue{\alpha}+l\mult\floor{\frac{n}{l}}=n\),
the string \(M[i_{\max}]^{\floor{\frac{n}{l}}}\alpha\)
is derivable following the scheme \(\rulename{(R1)}\) through
\(\rulename{(R4)}\) plus the increment rule \((M\to\#)\)\@. In such a
derivation the increment rule is applied
%
\[\sum_{i=1}^{\floor{\frac{n}{l}}}i_{\max}\mult(i_{\max}+1)^{i-1}\]
%
times\@. Then, with \(\rulename{(R4)}\), or \(\rulename{(R2)}\) if
necessary, we can change the rightmost digit (i.e., metasymbol) to
\([U]\): in doing so, the other digits change to \([0]\)\@. Again we
can add up (i.e., apply \((M\to\#)\) and the rules from the scheme)
and thus derive
\(M[i_{\max}]^{\floor{\frac{n}{l}}-1}[U]\alpha\)\@. Using this mechanism
several times, we can fill up the string with overflows \([U]\)\@. Thus,
we derive \(M[U]^{\floor{\frac{n}{l}}}\alpha\)\@.
%
\apar{Proof of Lemma 7-5}
Unless \(P_{\text{count}}\) contains some rules to fill up \(\alpha\),
now no more rules apply\@. The increment rule \((M\to\#)\) was applied
%
\[\sum_{i=1}^{\floor{\frac{n}{l}}}(i_{\max}+1)\mult(i_{\max}+1)^{i-1}=
(i_{\max}+1)\mult\sum_{i=0}^{\floor{\frac{n}{l}}-1}(i_{\max}+1)^{i}\]
%
times\@. If \(P_{\text{count}}\) contains some rules to fill up
\(\alpha\), that is, to do derivation steps
\([U]\alpha_{j}\derives{}[0]\alpha_{j+1}\),
where \(\alpha_{0}=\alpha\), \(\alpha_{j}\in N_{\text{count}}^{*}\)
for \(j\in \universe{N}\), the number of these steps is bounded by a
constant \(c\), independent of~\(n\)\@.
%
\apar{Proof of Lemma 7-6}
To derive \(M[U]^{\floor{\frac{n}{l}}}\alpha_{c}\), the increment rule
is used
%
\[(i_{\max}+1)\mult\sum_{i=0}^{\floor{\frac{n}{l}}-1}(i_{\max}+1)^{i}+
c\mult(i_{\max}+1)^{\floor{\frac{n}{l}}}\]
%
times\@. Thus, the capacity of the counter \(\counter{Z}_{s,G}\) can be 
estimated~by:
%
\begin{align*}
%
K_{\counter{Z}}(n) &\leq c\mult\ceiling{\growthfactor{w}^{l}-1 }^%
{\floor{\frac{n}{l}}}+\ceiling{\growthfactor{w}^{l}-1}\mult
\sum_{i=0}^{\floor{\frac{n}{l}}-1}\ceiling{\growthfactor{w}^{l}-1}^{i}\\
%
&=c\mult\ceiling{\growthfactor{w}^{l}-1}^{\floor{\frac{n}{l}}}+
\ceiling{\growthfactor{w}^{l}-1}\mult
\frac{\ceiling{\growthfactor{w}^{l}-1}^{\floor{\frac{n}{l}}}-1}%
{\ceiling{\growthfactor{w}^{l}-1}-1}\\
%
&=c\mult\ceiling{\growthfactor{w}^{l}-1}^{\floor{\frac{n}{l}}}+
\ceiling{\growthfactor{w}^{l}-1}^{\floor{\frac{n}{l}}}-1+
\frac{\ceiling{\growthfactor{w}^{l}-1}^{\floor{\frac{n}{l}}}-1}%
{\ceiling{\growthfactor{w}^{l}-1}-1}\\
%
&\leq(c+2)\mult\ceiling{\growthfactor{w}^{l}-1}^{\floor{\frac{n}{l}}} 
%
\end{align*}
\sentence
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 7}}
\end{alabsubtext}
%
\apar{5.2-12}
The upper bound stated in the lemma is optimal\@. That is, we can really
find a counter working according to this adding mechanism and reaching
the stated capacity\@. We put Lemma~8 with the exponent
rounded up instead of rounded down, only because of technical reasons in
the use of the lemma\@.
%
{\nopagebreakendpar
\begin{alabsubtext}{Lemma}{8}{}
%
Let \(s\) be an infinite steady strictly monotone increasing position 
valuation and \(G\in WGCSG_{s}\) with at least two different nonterminals,
and let \(c\in\universe{N}^{+}\)\@. Let \(l\in\universe{N}\)\@.
Then there exists an \(s\)-counter \(\counter{Z}\), that has a capacity
with
%
\[K_\counter{Z}(n)\geq c\mult
\ceiling{\growthfactor{w}(s)^{l}-1}^{\ceiling{\frac{n}{l}}}
\text{ for }n\in\universe{N}^{+}\text{, }n \geq l\]
\sentence
%
\end{alabsubtext}
}
%
\begin{alabsubtext}{Proof of Lemma}{8}{}
\prooffontshape
%
\apar{Proof of Lemma 8-1}
First we consider \(c=1\)\@. We define an \(s\)-counter
%
\[\counter{Z}=(N_{1},N_{2},N_{\text{count}},
(z_{n})_{n\in\universe{N}^{+}},P_{\text{count}})\]
%
following the scheme in Lemma~7\@. We will use the symbols of the string
that are not used in a digit, which only occurs if \(n\) is not
divisible by \(l\), to ``cheat'' by using them to encode an additional
digit\@. Thus we define:
%
\begin{align*}
%
N_{1} &\equdef\{M\} \qquad N_{2}\equdef\{\#\}\\
%
N_{\text{count}} &\equdef
%
\begin{aligned}[t]
%
&\left\{D,[0],[1],\dots,[i_{\max}],[U]\right\}\setunion
\left\{\langle 0\rangle,\langle1\rangle,\dots,\langle i_{\max}\rangle,
\langle U\rangle\right\}\\
%
&\lefteqn{\text{where }i_{\max}=\ceiling{\growthfactor{w}(s)^{l}-2}}
%
\end{aligned}
%
\end{align*}
\sentence
%
Each digit ``\(i\)'' is represented by \(D^{l-1}[i]\), 
and the start strings are \(z_{n}=
\left(D^{l-1}[0]\right)^{\floor{\frac{n}{l}}}\langle 0\rangle^{n\bmod l}\) 
for every \(n\in\universe{N}\)\@. The set \(P_{\text{count}}\) consists
of the following rules (where \(i=0,\dots,i_{\max}-1\)):
%
\begin{gather*}
%
\begin{alignedat}{4}
%
\rulename{(R1)} &\quad & \#D^{l-1}[i] &\to MD^{l-1}[i+1] & \qquad
\rulename{(R3)} &\quad & [U]D^{l-1}[i] &\to [0]D^{l-1}[i+1]\\
%
\rulename{(R2)} &\quad & \#D^{l-1}[i_{\max}] &\to MD^{l-1}[U] & \qquad
\rulename{(R4)} &\quad & [U]D^{l-1}[i_{\max}] &\to [0]D^{l-1}[U]
%
\end{alignedat}\\[3ex]
%
\begin{alignedat}{2}
%
\rulename{(R5)} &\quad & [U]\langle i\rangle &\to [0]\langle i+1\rangle\\
%
\rulename{(R6)} &\quad & [U]\langle i_{\max}\rangle &\to [0]\langle U\rangle
%
\end{alignedat}
%
\end{gather*}
\sentence
%
Now we define a symbol valuation 
\(f\oftype\funcspace{N_{1}\setunion N_{2}\setunion N_{\text{count}}}%
{\universe{N}^{+}}\) by (where \(i=1,\dots,i_{\max}\)):
%
\begin{alignat*}{3}
f(M) &\equdef 1\qquad & f(D) &\equdef 1\qquad & f(\#)
  &\equdef\ceiling{\growthfactor{w}(s)^{l}}\\
%
f([0]) &\equdef 1\qquad & f([i]) &\equdef i+1\qquad &
f([U]) &\equdef\ceiling{\growthfactor{w}(s)^{l}}\\
%
f(\langle 0\rangle) &\equdef 1\qquad &
f(\langle i\rangle) &\equdef i\mult\ceiling{\growthfactor{w}(s)^{l}}\qquad & 
f(\langle U\rangle)
  &\equdef\left(\ceiling{\growthfactor{w}(s)^{l}}-1\right)\mult
   \ceiling{\growthfactor{w}(s)^{l}}
%
\end{alignat*}
%
It can be checked easily that the given rules all are \(s\)-weakly 
growing with~\(f\)\@.
%
\apar{Proof of Lemma 8-2}
The rules \(\rulename{(R5)}\) and \(\rulename{(R6)}\) give us the
possibility to ``cheat'' by using an additional digit, if \(l\) does
not divide \(n\)\@. The capacity now is calculated just as in the proof
of Lemma~7, thus applies
\(K_\counter{Z}(n)\geq
\ceiling{\growthfactor{w}(s)^{l}-1}^{\ceiling{\frac{n}{l}}}\)\@.
By collecting weights we get a counter \(\counter{Z'}\) with 
\(K_\counter{Z'}=c\mult K_\counter{Z}\) for every \(c\in\universe{N}^{+}\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 8}}
\end{alabsubtext}
%
\asubsection{5.3}{Simulation of Time-Bounded Linear Automata}
%
\apar{5.3-1}
The counters introduced in Lemma~8 now will be used in a simulation of
a time-bounded linear-bounded automaton instead of the swallower we
used in Section~4\@. The time bounds for linear bounded automata that
can be managed with this counter are determined by the counter's
capacity\@.
%
\begin{alabsubtext}{Theorem}{7}{}
%
Let \(\growthfactor{w}\in\universe{N}^{+}\), let \(q\in\universe{Q}\)
with \(0<q<1\)\@. Then:
%
\[\complexityclass{\(T\)-NSPACE-TIME}\left(n,
\orderof{\growthfactor{w}^{q\mult n}}\right)\subseteq
\classoflang{WGCSL}_{\growthfactor{w}}\]
\sentence
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{7}{}
\prooffontshape
%
\apar{Proof of Theorem 7-1}
We only describe the intuitive operation of the grammar simulating a
given linear-bounded automaton on a given
\(\growthfactor{w}\in\universe{N}^{+}\)\@. The construction of the
grammar itself then is straightforward\@.
%
\apar{Proof of Theorem 7-2}
Let \(M\) be any linear bounded automaton that recognizes its language 
\(\gramtolang(M)\) in the time \(c\mult\growthfactor{w}^{q\mult n}\)
with an appropriate \(c\in\universe{N}^{+}\), and let \(s\) be an
infinite steady position valuation with
\(\growthfactor{w}(s)=\growthfactor{w}\)\@.
%
\apar{Proof of Theorem 7-3}
Similar to Section~4, case (iii), we divide the
sentential form into left-hand and right-hand parts: In the left-hand
part the step-by-step simulation of the automaton takes place in the
same manner as in the simulation mentioned above, except that we use
tape compression; in the right-hand part, a counter is situated (see
Figure~4)\@.
%
\begin{figure*}
\fbox{\parbox[t]{\textwidth}{%
%
\[\underbrace{\overbrace{\tapepair{\text{LBA simulation}}%
{\text{compressed}}\text{\rule{0ex}{3.6ex}}}^{\frac{1}{k}\mult n}
\overbrace{\underbrace{D^{l-1}[i_{1}]}_{\text{lowest digit}}
\underbrace{D^{l-1}[i_{2}]}_{\text{2.~digit}}\dots\text{\rule{0ex}{3.6ex}}
\underbrace{D^{l-1}[i_{\max}]}_{\text{highest
digit}}}^{\frac{k-1}{k}\mult n}
\text{\rule[-5ex]{0ex}{3.6ex}}}_%
{\text{length of the derived word (i.e., the original input)}}\]
}}
%
\afigcap{4}{Simulation with a steady position valuation: sentential form}
%
\end{figure*}
%
\apar{Proof of Theorem 7-4}
We choose an appropriate compression factor \(k\) so that 
\(q<\frac{k-1}{k}\), and for this \(k\) we choose the width \(l\) 
of a digit so that \(\ceiling{\growthfactor{w}^{l}}\geq
\growthfactor{w}^{l\mult q\mult\frac{k}{k-1}}+1\)\@.
Note that this expression is equivalent to 
\(\ceiling{\growthfactor{w}^{l}-1}^{\frac{k-1}{k}\mult\frac{1}{l}}\geq 
\growthfactor{w}^{q}\)\@.
%
\apar{Proof of Theorem 7-5}
Following Lemma~8 we can find an \(s\)-counter 
\(\counter{Z}\) with the capacity \(K_{\counter{Z}}(m)\geq
c\mult\ceiling{\left(\growthfactor{w}\right)^{l}-1}^{\ceiling{\frac{m}{l}}}\)
where \(m\equdef\ceiling{\frac{k-1}{k}\mult n}\) is the length of the part
of the sentential form where the counter operates in the simulation
for an input of length \(n\)\@. This implies
%
\[K_{\counter{Z}}(m)\geq
c\mult\ceiling{\growthfactor{w}^{l}-1}^%
{\ceiling{\frac{k-1}{k}\mult\frac{n}{l}}}\geq
c\mult\growthfactor{w}^{q\mult n}\]
\sentence
%
This means that if \(M\) accepts an input word, the simulation can be
completed\@. Then the \(k\)-tuples of the compressed LBA-simulation are
transformed into terminals and expanded at the same time\@. Together with
the expansion, the counter disappears\@.
%
\apar{Proof of Theorem 7-6}
This can be expressed by a \(\classofgrammar{WGCSG}\) with position
valuation \(s\) in the following way\@. First we state the length of
the sentential form is exactly \(n\), i.e., the length of the terminal
word to be produced\@. The reason is that the length of the part of
the sentential form where the counter operates is
\(m=\ceiling{\frac{k-1}{k}\mult n}\), as stated above, and the length
of the part where the simulation takes place can be organized such
that it equals \(\floor{\frac{1}{k}\mult n}\), e.g., by compressing
\(k\) symbols of the input for the LBA (the later terminal word) in
every simulation symbol, except for the rightmost one: Here we encode
\(k'\assigned k+n\bmod k\) symbols\@.
%
\apar{Proof of Theorem 7-7}
Now the decompression works in the following way: First, the rightmost
simulation symbol is transformed and decompressed into \(k'\) terminal
symbols, where \(k'-1\) of the (leftmost) counter symbols
disappear\@. Then the terminal symbols are passed through to the
right\@. By valuating the terminal symbols greater than the maximum
value of all other symbols, these rules are weakly growing related to
\(s\)\@. The same procedure is done with the now-rightmost symbol, and
then step by step with all the simulation symbols, where in this and
the following steps \({k'\assigned k}\)\@.
%
\apar{Proof of Theorem 7-8}
For a detailed and explicit construction of the grammar,
see~\cite{cj96-04-22}\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Theorem 7}}
\end{alabsubtext}
%
\apar{5.3-2}
Note that the requirement \(q<\frac{k-1}{k}\) is for a trick only: In
order to exceed the time bound with the capacity of the counter, we
strengthen it by the choice of \(l\), the number of letters
representing a digit (see Lemma~8, and regard
additionally the limited space for the counter in the simulating
sentential form)\@. But such an \(l\), fulfilling
\(\ceiling{\growthfactor{w}^{l}-1}^{\frac{k-1}{k}\mult n\mult\frac{1}{l}}\geq
\growthfactor{w}^{q\mult n}\),
does not exist for \(\frac{k-1}{k}\leq q\), so there is a gap between
Theorem~6 and Theorem~7\@. As the construction
technique used to build a counter with exponential capacity does not
lead further (see Lemma~7), closing this gap is a nontrivial problem\@.
%
{\par\raggedright
\asection{6}{Characterizing the Exponential Time \nohyphenl{Hierarchy}
of~\protect\(\classoflang{CSL}\protect\)} 
}
%
\apar{6-1}
In the previous sections we looked at several position valuations,
structuring and investigating them\@. Now we will gain an overview of
the different classes of weakly growing context-sensitive languages
related to different position valuations\@.
%
\apar{6-2}
For a constant position valuation, we obtain the same grammars as if
we had no position valuation at all, namely the quasi-growing
context-sensitive grammars, which characterize \(\classoflang{GCSL}\)
(\cite{cj96-04-07}, compare Section~2)\@. For every unsteady position
valuation, we obtain the language class
\(\classoflang{CSL}\), as we saw in Section~4\@.
Allowing zero points for position valuations, we also obtain a
characterization of \(\classoflang{CSL}\), as we mentioned before (see
Section~2)\@.
%
\apar{6-3}
Note that in Definition~3 we gave an equivalent characterization for
the property ``unsteady,'' which does not hold for position valuations
with zero points: A position valuation \(s\) without zero points is
unsteady if and only if \(s\) has at least three valuated positions
and \(s\) has a blip, i.e., a position \(j\) with \(s(j)^{2}\neq
s(j-1)\mult s(j+1)\)\@. In Section~4, in fact, we used this equivalent
characterization (e.g., in the values of the symbols of a
swallower)\@. Essentially, there is still something to show in cases
where \(s\) has only two valuated positions or where \(s\) has no blip
according to the definition given above, which is the case if \(s\)
has only one nonzero point, and this is the first or the last valuated
position, or if \(s\) has nonzero points at the first \emph{and} the
last position, separated at least by two zero points\@. On the other
hand, the proof technique we use for these cases works for each
position valuation with zero points\@. Therefore we formulate the next
theorem and give a proof here\@.
%
\begin{alabsubtext}{Theorem}{8}{}
%
Let \(s\) be a position valuation with zero points\@. Then:
%
\[\classoflang{WGCSL}_{s}=\classoflang{CSL}\]
\sentence
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{8}{}
\prooffontshape
%
\apar{Proof of Theorem 8-1}
It is sufficient to show
\(\classoflang{CSL}\subseteq\classoflang{WGCSL}_{s}\)\@.
And it is sufficient to show this claim for finite position valuations \(s\)\@.
So let \(s\) be a finite position valuation with zero points\@.
%
\apar{Proof of Theorem 8-2}
As the definition of \(\classoflang{WGCSL}_{s}\) implies that \(s\) is
not constantly \(0\), Theorem~2 applies, and thus
\(\classoflang{WGCSL}_{s}\) is closed under transposition\@.
Theorem~4 can be adapted in the following sense: Let \(m\) be the
greatest position valuated by \(s\)\@. Define
\(\overline{s}\oftype\funcspace{\universe{N}^{+}}{\universe{N}}\) by:
\(\overline{s}(i)\equdef s(m-i+1)\) for \(i=1,2,\dots,m\)\@.
Then \(\classoflang{WGCSL}_{s}=\classoflang{WGCSL}_{\overline{s}}\)\@.
%
\apar{Proof of Theorem 8-3}
This especially means we can assume that there exists a zero point
\(j\) with \(s(j+1)=c\neq 0\)\@. Regarding these two positions, the
``growth factor'' in fact is not defined, but it can be seen as
arbitrarily large\@. Thus, we can construct a counter similar to the
one in Section~5.2 that counts in an arbitrarily given number
representation\@. (For \(j\neq 1\) we add a left-hand context of length
\(j-1\) to the rules in the proof of Lemma~8, we can choose \(l=1\),
and the symbol valuation is constructed in the same way as it was
there\@.) Now given a linear bounded automaton with the exponential
time bound \(b^{n}=\left(b^{2}\right)^{\frac{1}{2}\mult n}\), \(b\geq 2\),
we construct a grammar similar to the one