
\setcounter{figure}{34}
\setcounter{table}{3}
\chapter{text}
\newpage



%        Now we can begin the characterization.  The easiest way to
%        present the characterization is to go back to string re-writing
%        rules as we did for 2 x m grids.  Since the 4 x 2, 4 x 3, and 4
%        x 4 patterns have already been given, the rules will begin with
%        a 4 x 5 grid.  This grid has the string AC.  The first rule is
%        that whenever there is a C replace it with DB.  Therefore a 4 x
%        6 grid is ADB.  The next rule is that whenever there is a B
%        replace it with a C.  Therefore for $m \geq 4$ 
	\noindent
	and  m even, the
        string is an A at the beginning, a B at the end and there are
        $(m/2)-2$ D's in between.   If m is odd and $m \geq 5$, the
        string is an A at the beginning, a C at the end, and $((m-1)/2)
        - 2$ D's in between.  A listing of the strings for m from 5 to
        11 is given in Table~\ref{table:grid.4.m}.

        \begin{table}[h]
        \vspace*{22pt}
        \caption{\label{table:grid.4.m} String representations for 4 x m grids.}
        \begin{center}
        \begin{tabular}{|r|c|c|c|c|c|c|c|}\hline
         m = & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline
         String& ${\cal AC}$ & ${\cal ADB}$ & ${\cal ADC}$ & ${\cal ADDB}$ &
               ${\cal ADDC}$ & ${\cal ADDDB}$ & ${\cal ADDDC}$
                \\ \hline
        \end{tabular}
        \end{center}
        \vspace*{22pt}
        \end{table}


        \hspace*{11pt}
        \subsection{Computation Times}

	In their work on grids, Cockayne and Hewgill [25] also discussed
	the computation time
        and presented graphs for both the time necessary to generate of
        T\_list, and to extract the proper answer from T\_list.  These
        graphs both increase exponentially as the number of points in
        the grid increases.  The interresting thing that can be gleaned
        from the graphs was the comparison of grids  with randomly
        generated problems.  This comparison was only presented for the
        computation of T\_list, but it showed that the time to generate
        T\_list for a grid with 25 points exceeded the average time to
        generate T\_list for a randomly generated 100 point problem.
        From our work we also saw results that matched the basic
        structure of these curves. The T\_list curve was stretched
        horizontally a bit due to the parallelism introduced.

