\documentstyle[11pt]{article}
\sloppy
\newcommand{\xbar}{\overline{x}}
\newlength{\mylength}
\newcounter{robifigure}
\def\therobifigure{\arabic{robifigure}}
\def\caption#1{\refstepcounter{robifigure}
 \figurename\enspace\therobifigure. #1}%\medskip\par}
\def\endrobifigure{}

\author{
 Robert Stoyan\thanks{rtstoyan@cip.informatik.uni-erlangen.de}\\
 Volker Strehl\thanks{strehl@immd1.informatik.uni-erlangen.de}\\
 Computer Science Department (Informatik)\\
 University of Erlangen-N\"urnberg\\
 D-91058 Erlangen, Germany}

\date{[ \small Note: this article has been accepted for publication by the\\
{\it Journal of Combinatorial Mathematics and Combinatorial Computing}]}

\title{Enumeration of Hamiltonian Circuits in Rectangular Grids}
 
\begin{document}
\maketitle

\begin{abstract}
 \noindent
 We describe an algorithm for computing the number $h_{m,n}$ of 
 Hamiltonian circuits in a rectangular grid graph consisting of 
 $m\times n$ squares. 
 For any fixed $m$, the set of Hamiltonian circuits on such graphs 
 (for varying $n$) can be identified via an appropriate coding 
 with the words of a certain regular language 
 $L_m \subset \left(\{0,1\}^m\right)^*$. 
 We show how to systematically construct a finite automaton ${\cal A}_m$ 
 recognizing $L_m$. This allows, in principle,
 the computation of the (rational) generating function $h_m(z)$ of $L_m$.
 We exhibit a bijection between the states of ${\cal A}_m$ and the words
 of length $m+1$ of the familiar Motzkin language. This yields an
 upper bound on the degree of the denominator polynomial of $h_m(z)$,
 hence of the order of the linear recurrence satisfied by the coefficients
 $h_{m,n}$ for fixed $m$. 
 
 The method described here has been implemented. Numerical data resulting
 from this implementation are presented at the end of this article. 

\end{abstract}
\newpage
\section{Introduction}

We consider the problem of enumerating Hamiltonian circuits on rectangular grid 
graphs.

\begin{center} 
\unitlength=0.7mm
\linethickness{0.4pt}
\begin{picture}(61.00,28.00)
\put(6.00,22.00){\circle{2.00}}
\put(7.00,22.00){\line(1,0){4.00}}
\put(6.00,17.00){\line(0,1){4.00}}
\put(6.00,16.00){\circle{2.00}}
\put(7.00,16.00){\line(1,0){4.00}}
\put(6.00,11.00){\line(0,1){4.00}}
\put(12.00,22.00){\circle{2.00}}
\put(13.00,22.00){\line(1,0){4.00}}
\put(12.00,17.00){\line(0,1){4.00}}
\put(12.00,16.00){\circle{2.00}}
\put(13.00,16.00){\line(1,0){4.00}}
\put(12.00,11.00){\line(0,1){4.00}}
\put(18.00,22.00){\circle{2.00}}
\put(19.00,22.00){\line(1,0){4.00}}
\put(18.00,17.00){\line(0,1){4.00}}
\put(18.00,16.00){\circle{2.00}}
\put(19.00,16.00){\line(1,0){4.00}}
\put(18.00,11.00){\line(0,1){4.00}}
\put(24.00,22.00){\circle{2.00}}
\put(24.00,17.00){\line(0,1){4.00}}
\put(24.00,16.00){\circle{2.00}}
\put(24.00,11.00){\line(0,1){4.00}}
\put(6.00,10.00){\circle{2.00}}
\put(7.00,10.00){\line(1,0){4.00}}
\put(12.00,10.00){\circle{2.00}}
\put(13.00,10.00){\line(1,0){4.00}}
\put(18.00,10.00){\circle{2.00}}
\put(19.00,10.00){\line(1,0){4.00}}
\put(24.00,10.00){\circle{2.00}}
\put(6.00,5.00){\line(0,1){4.00}}
\put(6.00,4.00){\circle{2.00}}
\put(7.00,4.00){\line(1,0){4.00}}
\put(12.00,5.00){\line(0,1){4.00}}
\put(12.00,4.00){\circle{2.00}}
\put(13.00,4.00){\line(1,0){4.00}}
\put(18.00,5.00){\line(0,1){4.00}}
\put(18.00,4.00){\circle{2.00}}
\put(19.00,4.00){\line(1,0){4.00}}
\put(24.00,5.00){\line(0,1){4.00}}
\put(24.00,4.00){\circle{2.00}}
\put(25.00,22.00){\line(1,0){4.00}}
\put(25.00,16.00){\line(1,0){4.00}}
\put(30.00,22.00){\circle{2.00}}
\put(31.00,22.00){\line(1,0){4.00}}
\put(30.00,17.00){\line(0,1){4.00}}
\put(30.00,16.00){\circle{2.00}}
\put(31.00,16.00){\line(1,0){4.00}}
\put(30.00,11.00){\line(0,1){4.00}}
\put(36.00,22.00){\circle{2.00}}
\put(37.00,22.00){\line(1,0){4.00}}
\put(36.00,17.00){\line(0,1){4.00}}
\put(36.00,16.00){\circle{2.00}}
\put(37.00,16.00){\line(1,0){4.00}}
\put(36.00,11.00){\line(0,1){4.00}}
\put(42.00,22.00){\circle{2.00}}
\put(42.00,17.00){\line(0,1){4.00}}
\put(42.00,16.00){\circle{2.00}}
\put(42.00,11.00){\line(0,1){4.00}}
\put(25.00,10.00){\line(1,0){4.00}}
\put(30.00,10.00){\circle{2.00}}
\put(31.00,10.00){\line(1,0){4.00}}
\put(36.00,10.00){\circle{2.00}}
\put(37.00,10.00){\line(1,0){4.00}}
\put(42.00,10.00){\circle{2.00}}
\put(25.00,4.00){\line(1,0){4.00}}
\put(30.00,5.00){\line(0,1){4.00}}
\put(30.00,4.00){\circle{2.00}}
\put(31.00,4.00){\line(1,0){4.00}}
\put(36.00,5.00){\line(0,1){4.00}}
\put(36.00,4.00){\circle{2.00}}
\put(37.00,4.00){\line(1,0){4.00}}
\put(42.00,5.00){\line(0,1){4.00}}
\put(42.00,4.00){\circle{2.00}}
\put(43.00,22.00){\line(1,0){4.00}}
\put(43.00,16.00){\line(1,0){4.00}}
\put(48.00,22.00){\circle{2.00}}
\put(49.00,22.00){\line(1,0){4.00}}
\put(48.00,17.00){\line(0,1){4.00}}
\put(48.00,16.00){\circle{2.00}}
\put(49.00,16.00){\line(1,0){4.00}}
\put(48.00,11.00){\line(0,1){4.00}}
\put(54.00,22.00){\circle{2.00}}
\put(55.00,22.00){\line(1,0){4.00}}
\put(54.00,17.00){\line(0,1){4.00}}
\put(54.00,16.00){\circle{2.00}}
\put(55.00,16.00){\line(1,0){4.00}}
\put(54.00,11.00){\line(0,1){4.00}}
\put(60.00,22.00){\circle{2.00}}
\put(60.00,17.00){\line(0,1){4.00}}
\put(60.00,16.00){\circle{2.00}}
\put(60.00,11.00){\line(0,1){4.00}}
\put(43.00,10.00){\line(1,0){4.00}}
\put(48.00,10.00){\circle{2.00}}
\put(49.00,10.00){\line(1,0){4.00}}
\put(54.00,10.00){\circle{2.00}}
\put(55.00,10.00){\line(1,0){4.00}}
\put(60.00,10.00){\circle{2.00}}
\put(43.00,4.00){\line(1,0){4.00}}
\put(48.00,5.00){\line(0,1){4.00}}
\put(48.00,4.00){\circle{2.00}}
\put(49.00,4.00){\line(1,0){4.00}}
\put(54.00,5.00){\line(0,1){4.00}}
\put(54.00,4.00){\circle{2.00}}
\put(55.00,4.00){\line(1,0){4.00}}
\put(60.00,5.00){\line(0,1){4.00}}
\put(60.00,4.00){\circle{2.00}}
\put(6.00,28.00){\makebox(0,0)[ct]{0}}
\put(60.00,28.00){\makebox(0,0)[ct]{n}}
\put(2.00,22.00){\makebox(0,0)[cc]{0}}
\put(3.00,4.00){\makebox(0,0)[rc]{m}}
\end{picture}

\end{center}
\caption{The grid graph $G_{3,9}^*$}\label{graph}

\bigskip

Let $h_{m,n}$ denote the number of 
Hamiltonian circuits on a grid graph with
$(m+1) \times (n+1)$ vertices as in 
Fig.~\ref{graph}, and let
\[
h_m(z) = \sum\limits_{n \geq 1} h_{m,n} z^n
\]
denote the associated generating function for fixed $m$. 
The main goal of this article is to outline an algorithm which allows 
to systematically compute --- in principle --- $h_{m}(z)$ for
any $m$. It turns out that $h_m(z)$ is always a rational function, 
a fact that has been observed by authors who studied this enumeration 
problem for small values of $m$ by {\em ad hoc} methods 
(\cite{kreweras},\cite{kwong},\cite{rogers}). 
This result is an immediate consequence of the transfer-matrix method, 
which we employ here for the general approach. See Sec. 4.7 in \cite{stanley}
for a presentation of this method.  
Indeed, we show how Hamiltonian circuits on grid graphs can be encoded 
by the words of a suitable language that is recognized by a finite automaton. 
Note that Hamiltonicity of a graph has both a local (every vertex is 
visited exactly once) and a global (the subgraph is connected) aspect. 
It is quite obvious how to code the local aspect in a way
that can be checked by a finite automaton.
It is less obvious how the same can be done for the global aspect in 
a systematical way. This is the main contribution of the 
present article. 

Once a coding in terms of a regular language has been 
given and a recognizing finite automaton has been constructed,
the computation of the generating function 
$h_m(z)$ is a routine matter --- in principle! 
In practice there are severe limits due to the exponentially increasing
number of states (as a function of $m$). Indeed, 
we can give precise information about
the number of states of our automata (prior to 
minimization) and thus an upper
bound for the degree of the denominator polynomial 
of $h_m(z)$. Interestingly, the states
can be put into bijection with the words of the 
familiar Motzkin language. Even though
minimization may cut down the number of states considerably 
(for $m$ odd about half of the original states turn out to 
be non-reachable), we conjecture that the growth of 
the degrees of the denominator polynomials of $h_m(z)$ is 
of the same order as that of the Motzkin numbers.


We refer the reader to \cite{hu} for the basic notions
of automata theory needed here, and \cite{br}
for the relation between regular languages and rational
generating functions. 


The algorithm outlined here has been implemented by the 
first author (\cite{stoyan}). For efficiency reasons, this implementation 
uses a slightly different way of representing the automaton 
in question, which we will not discuss here. 
The program, written in the C++ language, and a complete description of its 
functionality are available on request from the first author. 
At the end of this article we present some results obtained 
by this program.

\section{Representation and characterization}

We begin by introducing some notation:

For positive integers $m,n$ the grid graph $G_{m,n}$
is given by its vertex set 
$ \{\,(x,y) \,;\, 1 \leq x \leq n , 1 \leq y \leq m \,\}$ 
and the usual nearest-neighbour-edges of a rectangular grid.

It is convenient for our purposes to introduce also the
extended grid graph $G_{m,n}^*$ with vertex set
$ \{\,(x,y) \,;\, 0 \leq x \leq n , 0 \leq y \leq m \,\}$.
See Fig.~\ref{graph} for an example.

A ``cell'' of $G_{m,n}^*$ is a quadrangle of points
\[
[x,y] = \{(x,y), (x-1,y), (x,y-1), (x-1, y-1) \}
\]
where $1 \leq x \leq n , 1 \leq y \leq m$. 
Think of $G_{m,n}$ as a graph whose vertices are the cells of $G_{m,n}^*$, 
and edges in $G_{m,n}$ joining neighbouring cells in $G_{m,n}^*$ 
(i.e. cells which have an edge of $G_{m,n}^*$ in common).

A {\em Hamiltonian circuit} of $G_{m,n}^*$ is a subgraph $H^*$ of $G_{m,n}^*$
with the following properties:
\begin{itemize}
\item[-]
every vertex $(x,y)$ has degree $2$ w.r.t. $H^*$
\item[-]
$H^*$ is connected
\end{itemize}
By a discrete version of the Jordan curve theorem 
it is clear that each cell $[x,y]$ of $G_{m,n}^*$ 
lies either ``inside'' or ``outside'' such a Hamiltonian
circuit $H^*$. This gives rise to a mapping
\[
H : G_{m,n} \rightarrow \{ 0,1 \} : (x,y) \mapsto
\cases{
1& if  $[x,y]$  is an ``inside'' cell w.r.t. $H^*$\cr
0& if  $[x,y]$  is an ``outside'' cell  w.r.t. $H^*$
}
\]
Let now $F : G_{m,n} \rightarrow \{ 0,1 \}$ be any mapping. We will use the 
same notation $F$ for different presentations of the same object:
\begin{itemize}
\item[-]
a mapping from (the vertex set of) $G_{m,n}$ to $\{ 0,1 \}$, as indicated;
\item[-]
the corresponding $(m \times n)$-matrix which has entry $F(x,y)$ in position $(x,y)$;
\item[-]
the {\em induced} subgraph of $G_{m,n}$ with vertex set $F^{-1} (1)$;
\item[-]
the word $F^{(1)} F^{(2)} \ldots F^{(n)}$ over the alphabet 
$\Sigma_m := \{ 0,1 \}^m$ where $F^{(k)}$ denotes the $k$-th column
of the matrix $F$, written as a word over $\Sigma_m$, for convenience.
\end{itemize} 

\begin{center}
\unitlength=0.7mm
\linethickness{0.4pt}
\begin{picture}(180.00,30.00)(1.50,4)
\put(4.00,33.00){\line(1,0){4.00}}
\put(3.00,28.00){\line(0,1){4.00}}
\put(4.00,27.00){\line(1,0){4.00}}
\put(3.00,16.00){\line(0,1){4.00}}
\put(4.00,15.00){\line(1,0){4.00}}
\put(3.00,10.00){\line(0,1){4.00}}
\put(10.00,33.00){\line(1,0){4.00}}
\put(9.00,28.00){\line(0,1){4.00}}
\put(10.00,27.00){\line(1,0){4.00}}
\put(9.00,16.00){\line(0,1){4.00}}
\put(10.00,15.00){\line(1,0){4.00}}
\put(9.00,10.00){\line(0,1){4.00}}
\put(15.00,33.00){\circle{2.00}}
\put(16.00,33.00){\line(1,0){4.00}}
\put(15.00,28.00){\line(0,1){4.00}}
\put(15.00,21.00){\circle{2.00}}
\put(16.00,27.00){\line(1,0){4.00}}
\put(15.00,16.00){\line(0,1){4.00}}
\put(16.00,15.00){\line(1,0){4.00}}
\put(15.00,10.00){\line(0,1){4.00}}
\put(21.00,33.00){\circle{2.00}}
\put(21.00,28.00){\line(0,1){4.00}}
\put(21.00,21.00){\circle{2.00}}
\put(21.00,16.00){\line(0,1){4.00}}
\put(21.00,15.00){\circle{2.00}}
\put(21.00,10.00){\line(0,1){4.00}}
\put(3.00,9.00){\circle{2.00}}
\put(4.00,9.00){\line(1,0){4.00}}
\put(9.00,9.00){\circle{2.00}}
\put(10.00,9.00){\line(1,0){4.00}}
\put(15.00,9.00){\circle{2.00}}
\put(16.00,9.00){\line(1,0){4.00}}
\put(21.00,9.00){\circle{2.00}}
\put(3.00,4.00){\line(0,1){4.00}}
\put(3.00,3.00){\circle{2.00}}
\put(4.00,3.00){\line(1,0){4.00}}
\put(9.00,4.00){\line(0,1){4.00}}
\put(9.00,3.00){\circle{2.00}}
\put(10.00,3.00){\line(1,0){4.00}}
\put(15.00,4.00){\line(0,1){4.00}}
\put(15.00,3.00){\circle{2.00}}
\put(16.00,3.00){\line(1,0){4.00}}
\put(21.00,4.00){\line(0,1){4.00}}
\put(21.00,3.00){\circle{2.00}}
\put(22.00,33.00){\line(1,0){4.00}}
\put(22.00,27.00){\line(1,0){4.00}}
\put(22.00,15.00){\line(1,0){4.00}}
\put(27.00,33.00){\circle{2.00}}
\put(28.00,33.00){\line(1,0){4.00}}
\put(27.00,28.00){\line(0,1){4.00}}
\put(27.00,21.00){\circle{2.00}}
\put(28.00,27.00){\line(1,0){4.00}}
\put(27.00,16.00){\line(0,1){4.00}}
\put(27.00,15.00){\circle{2.00}}
\put(28.00,15.00){\line(1,0){4.00}}
\put(27.00,10.00){\line(0,1){4.00}}
\put(33.00,33.00){\circle{2.00}}
\put(34.00,33.00){\line(1,0){4.00}}
\put(33.00,28.00){\line(0,1){4.00}}
\put(33.00,21.00){\circle{2.00}}
\put(34.00,27.00){\line(1,0){4.00}}
\put(33.00,16.00){\line(0,1){4.00}}
\put(33.00,15.00){\circle{2.00}}
\put(34.00,15.00){\line(1,0){4.00}}
\put(33.00,10.00){\line(0,1){4.00}}
\put(39.00,33.00){\circle{2.00}}
\put(39.00,28.00){\line(0,1){4.00}}
\put(39.00,21.00){\circle{2.00}}
\put(39.00,16.00){\line(0,1){4.00}}
\put(39.00,15.00){\circle{2.00}}
\put(39.00,10.00){\line(0,1){4.00}}
\put(22.00,9.00){\line(1,0){4.00}}
\put(27.00,9.00){\circle{2.00}}
\put(28.00,9.00){\line(1,0){4.00}}
\put(33.00,9.00){\circle{2.00}}
\put(34.00,9.00){\line(1,0){4.00}}
\put(39.00,9.00){\circle{2.00}}
\put(22.00,3.00){\line(1,0){4.00}}
\put(27.00,4.00){\line(0,1){4.00}}
\put(28.00,3.00){\line(1,0){4.00}}
\put(33.00,4.00){\line(0,1){4.00}}
\put(33.00,3.00){\circle{2.00}}
\put(34.00,3.00){\line(1,0){4.00}}
\put(39.00,4.00){\line(0,1){4.00}}
\put(39.00,3.00){\circle{2.00}}
\put(40.00,33.00){\line(1,0){4.00}}
\put(40.00,27.00){\line(1,0){4.00}}
\put(40.00,15.00){\line(1,0){4.00}}
\put(45.00,33.00){\circle{2.00}}
\put(46.00,33.00){\line(1,0){4.00}}
\put(45.00,28.00){\line(0,1){4.00}}
\put(45.00,21.00){\circle{2.00}}
\put(46.00,27.00){\line(1,0){4.00}}
\put(45.00,16.00){\line(0,1){4.00}}
\put(46.00,15.00){\line(1,0){4.00}}
\put(45.00,10.00){\line(0,1){4.00}}
\put(51.00,33.00){\circle{2.00}}
\put(52.00,33.00){\line(1,0){4.00}}
\put(51.00,28.00){\line(0,1){4.00}}
\put(51.00,21.00){\circle{2.00}}
\put(52.00,27.00){\line(1,0){4.00}}
\put(51.00,16.00){\line(0,1){4.00}}
\put(51.00,15.00){\circle{2.00}}
\put(52.00,15.00){\line(1,0){4.00}}
\put(51.00,10.00){\line(0,1){4.00}}
\put(57.00,33.00){\circle{2.00}}
\put(57.00,28.00){\line(0,1){4.00}}
\put(57.00,21.00){\circle{2.00}}
\put(57.00,16.00){\line(0,1){4.00}}
\put(57.00,15.00){\circle{2.00}}
\put(57.00,10.00){\line(0,1){4.00}}
\put(40.00,9.00){\line(1,0){4.00}}
\put(45.00,9.00){\circle{2.00}}
\put(46.00,9.00){\line(1,0){4.00}}
\put(51.00,9.00){\circle{2.00}}
\put(52.00,9.00){\line(1,0){4.00}}
\put(57.00,9.00){\circle{2.00}}
\put(40.00,3.00){\line(1,0){4.00}}
\put(45.00,4.00){\line(0,1){4.00}}
\put(45.00,3.00){\circle{2.00}}
\put(46.00,3.00){\line(1,0){4.00}}
\put(51.00,4.00){\line(0,1){4.00}}
\put(51.00,3.00){\circle{2.00}}
\put(52.00,3.00){\line(1,0){4.00}}
\put(57.00,4.00){\line(0,1){4.00}}

\put(15.00,15.00){\circle*{2.00}}
\put(9.00,15.00){\circle*{2.00}}
\put(9.00,21.00){\circle*{2.00}}
\put(9.00,33.00){\circle*{2.00}}
\put(3.00,33.00){\circle*{2.00}}
\put(3.00,21.00){\circle*{2.00}}
\put(3.00,15.00){\circle*{2.00}}
\put(3.00,9.00){\circle*{2.00}}
\put(3.00,3.00){\circle*{2.00}}
\put(3.00,15.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(3.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(3.00,32.00){\rule{6.00\unitlength}{1.00\unitlength}}
\put(8.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(9.00,20.00){\rule{6.00\unitlength}{1.00\unitlength}}
\put(3.00,15.00){\rule{12.00\unitlength}{1.00\unitlength}}




\put(15.00,21.00){\circle*{2.00}}
\put(15.00,33.00){\circle*{2.00}}
\put(21.00,33.00){\circle*{2.00}}
\put(21.00,21.00){\circle*{2.00}}
\put(27.00,21.00){\circle*{2.00}}
\put(27.00,33.00){\circle*{2.00}}
\put(33.00,33.00){\circle*{0.00}}
\put(33.00,33.00){\circle*{2.00}}
\put(39.00,33.00){\circle*{2.00}}
\put(45.00,33.00){\circle*{2.00}}
\put(51.00,33.00){\circle*{2.00}}
\put(57.00,33.00){\circle*{2.00}}
\put(57.00,21.00){\circle*{2.00}}
\put(51.00,21.00){\circle*{2.00}}
\put(45.00,21.00){\circle*{2.00}}
\put(39.00,21.00){\circle*{2.00}}
\put(33.00,21.00){\circle*{2.00}}
\put(21.00,15.00){\circle*{2.00}}
\put(27.00,15.00){\circle*{2.00}}
\put(33.00,15.00){\circle*{2.00}}
\put(15.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(15.00,32.00){\rule{6.00\unitlength}{1.00\unitlength}}
\put(20.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(21.00,20.00){\rule{6.00\unitlength}{1.00\unitlength}}
\put(27.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(27.00,32.00){\rule{30.00\unitlength}{1.00\unitlength}}
\put(56.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(3.00,8.00){\rule{12.00\unitlength}{1.00\unitlength}}
\put(9.00,9.00){\circle*{2.00}}
\put(15.00,9.00){\circle*{2.00}}
\put(9.00,3.00){\circle*{2.00}}
\put(15.00,3.00){\circle*{2.00}}
\put(21.00,3.00){\circle*{2.00}}
\put(21.00,9.00){\circle*{2.00}}
\put(27.00,9.00){\circle*{2.00}}
\put(27.00,3.00){\circle*{2.00}}
\put(33.00,3.00){\circle*{2.00}}
\put(33.00,9.00){\circle*{2.00}}
\put(39.00,9.00){\circle*{2.00}}
\put(39.00,3.00){\circle*{2.00}}
\put(45.00,3.00){\circle*{2.00}}
\put(51.00,3.00){\circle*{2.00}}
\put(57.00,3.00){\circle*{2.00}}
\put(57.00,9.00){\circle*{2.00}}
\put(51.00,9.00){\circle*{2.00}}
\put(45.00,9.00){\circle*{2.00}}
\put(39.00,15.00){\circle*{2.00}}
\put(45.00,15.00){\circle*{0.00}}
\put(51.00,15.00){\circle*{2.00}}
\put(57.00,15.00){\circle*{2.00}}
\put(45.00,15.00){\circle*{2.00}}
\put(44.00,9.00){\rule{1.00\unitlength}{12.00\unitlength}}
\put(56.00,27.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(45.00,8.00){\rule{6.00\unitlength}{1.00\unitlength}}
\put(51.00,9.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(51.00,14.00){\rule{6.00\unitlength}{1.00\unitlength}}
\put(56.00,3.00){\rule{1.00\unitlength}{12.00\unitlength}}
\put(33.00,3.00){\rule{24.00\unitlength}{1.00\unitlength}}
\put(33.00,8.00){\rule{6.00\unitlength}{1.00\unitlength}}
\put(39.00,9.00){\rule{1.00\unitlength}{12.00\unitlength}}
\put(44.00,9.00){\rule{1.00\unitlength}{12.00\unitlength}}
\put(51.00,9.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(51.00,14.00){\rule{6.00\unitlength}{1.00\unitlength}}
\put(33.00,27.00){\rule{6.00\unitlength}{1.00\unitlength}}
\put(15.00,9.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(26.00,3.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(21.00,8.00){\rule{6.00\unitlength}{1.00\unitlength}}
\put(20.00,9.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(21.00,15.00){\rule{12.00\unitlength}{1.00\unitlength}}
\put(32.00,15.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(33.00,3.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(3.00,3.00){\rule{24.00\unitlength}{1.00\unitlength}}
\put(3.00,3.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(3.00,27.00){\circle*{2.00}}
\put(9.00,27.00){\circle*{2.00}}
\put(15.00,27.00){\circle*{2.00}}
\put(27.00,27.00){\circle*{2.00}}
\put(33.00,27.00){\circle*{2.00}}
\put(39.00,27.00){\circle*{2.00}}
\put(45.00,27.00){\circle*{2.00}}
\put(51.00,27.00){\circle*{2.00}}
\put(57.00,27.00){\circle*{2.00}}
\put(21.00,27.00){\circle*{2.00}}
\put(4.00,21.00){\line(1,0){4.00}}
\put(16.00,21.00){\line(1,0){4.00}}
\put(28.00,21.00){\line(1,0){4.00}}
\put(34.00,21.00){\line(1,0){4.00}}
\put(40.00,21.00){\line(1,0){4.00}}
\put(46.00,21.00){\line(1,0){4.00}}
\put(3.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(8.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(15.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(20.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(27.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(32.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(39.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(44.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(51.00,21.00){\rule{6.00\unitlength}{1.00\unitlength}}
\put(45.00,27.00){\rule{6.00\unitlength}{1.00\unitlength}}
\put(51.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}}
\put(56.00,21.00){\rule{1.00\unitlength}{6.00\unitlength}}


\put(-2.00,0.00)
{
	\put(73.00,30.00){\makebox(0,0)[cc]{1}}
	\put(79.00,30.00){\makebox(0,0)[cc]{0}}
	\put(85.00,30.00){\makebox(0,0)[cc]{1}}
	\put(91.00,30.00){\makebox(0,0)[cc]{0}}
	\put(97.00,30.00){\makebox(0,0)[cc]{1}}
	\put(103.00,30.00){\makebox(0,0)[cc]{1}}
	\put(109.00,30.00){\makebox(0,0)[cc]{1}}
	\put(115.00,30.00){\makebox(0,0)[cc]{1}}
	\put(121.00,30.00){\makebox(0,0)[cc]{1}}
	\put(73.00,18.00){\makebox(0,0)[cc]{1}}
	\put(79.00,18.00){\makebox(0,0)[cc]{1}}
	\put(85.00,18.00){\makebox(0,0)[cc]{1}}
	\put(91.00,18.00){\makebox(0,0)[cc]{1}}
	\put(97.00,18.00){\makebox(0,0)[cc]{1}}
	\put(103.00,18.00){\makebox(0,0)[cc]{0}}
	\put(109.00,18.00){\makebox(0,0)[cc]{1}}
	\put(115.00,18.00){\makebox(0,0)[cc]{0}}
	\put(121.00,18.00){\makebox(0,0)[cc]{0}}
	\put(73.00,6.00){\makebox(0,0)[cc]{1}}
	\put(79.00,6.00){\makebox(0,0)[cc]{1}}
	\put(79.00,12.00){\makebox(0,0)[cc]{0}}
	\put(73.00,12.00){\makebox(0,0)[cc]{0}}
	\put(85.00,12.00){\makebox(0,0)[cc]{1}}
	\put(91.00,12.00){\makebox(0,0)[cc]{0}}
	\put(97.00,12.00){\makebox(0,0)[cc]{0}}
	\put(103.00,12.00){\makebox(0,0)[cc]{0}}
	\put(109.00,12.00){\makebox(0,0)[cc]{1}}
	\put(115.00,12.00){\makebox(0,0)[cc]{0}}
	\put(121.00,12.00){\makebox(0,0)[cc]{1}}
	\put(85.00,6.00){\makebox(0,0)[cc]{1}}
	\put(91.00,6.00){\makebox(0,0)[cc]{1}}
	\put(97.00,6.00){\makebox(0,0)[cc]{0}}
	\put(103.00,6.00){\makebox(0,0)[cc]{1}}
	\put(109.00,6.00){\makebox(0,0)[cc]{1}}
	\put(115.00,6.00){\makebox(0,0)[cc]{1}}
	\put(121.00,6.00){\makebox(0,0)[cc]{1}}
	\put(79.00,24.00){\makebox(0,0)[cc]{0}}
	\put(73.00,24.00){\makebox(0,0)[cc]{1}}
	\put(85.00,24.00){\makebox(0,0)[cc]{1}}
	\put(91.00,24.00){\makebox(0,0)[cc]{0}}
	\put(97.00,24.00){\makebox(0,0)[cc]{1}}
	\put(103.00,24.00){\makebox(0,0)[cc]{0}}
	\put(109.00,24.00){\makebox(0,0)[cc]{1}}
	\put(115.00,24.00){\makebox(0,0)[cc]{0}}
	\put(121.00,24.00){\makebox(0,0)[cc]{1}}
	\put(70.00,33.00){\line(0,-1){30.00}}
	\put(70.00,33.00){\line(1,0){6.00}}
	\put(70.00,27.00){\line(1,0){6.00}}
	\put(70.00,21.00){\line(1,0){6.00}}
	\put(70.00,15.00){\line(1,0){6.00}}
	\put(70.00,9.00){\line(1,0){6.00}}
	\put(70.00,3.00){\line(1,0){6.00}}
	\put(76.00,33.00){\line(0,-1){30.00}}
	\put(76.00,33.00){\line(1,0){6.00}}
	\put(76.00,27.00){\line(1,0){6.00}}
	\put(76.00,21.00){\line(1,0){6.00}}
	\put(76.00,15.00){\line(1,0){6.00}}
	\put(76.00,9.00){\line(1,0){6.00}}
	\put(76.00,3.00){\line(1,0){6.00}}
	\put(82.00,33.00){\line(0,-1){30.00}}
	\put(82.00,33.00){\line(1,0){6.00}}
	\put(82.00,27.00){\line(1,0){6.00}}
	\put(82.00,21.00){\line(1,0){6.00}}
	\put(82.00,15.00){\line(1,0){6.00}}
	\put(82.00,9.00){\line(1,0){6.00}}
	\put(82.00,3.00){\line(1,0){6.00}}
	\put(88.00,33.00){\line(0,-1){30.00}}
	\put(88.00,33.00){\line(1,0){6.00}}
	\put(88.00,27.00){\line(1,0){6.00}}
	\put(88.00,21.00){\line(1,0){6.00}}
	\put(88.00,15.00){\line(1,0){6.00}}
	\put(88.00,9.00){\line(1,0){6.00}}
	\put(88.00,3.00){\line(1,0){6.00}}
	\put(94.00,33.00){\line(0,-1){30.00}}
	\put(94.00,33.00){\line(1,0){6.00}}
	\put(94.00,27.00){\line(1,0){6.00}}
	\put(94.00,21.00){\line(1,0){6.00}}
	\put(94.00,15.00){\line(1,0){6.00}}
	\put(94.00,9.00){\line(1,0){6.00}}
	\put(94.00,3.00){\line(1,0){6.00}}
	\put(100.00,33.00){\line(0,-1){30.00}}
	\put(100.00,33.00){\line(1,0){6.00}}
	\put(100.00,27.00){\line(1,0){6.00}}
	\put(100.00,21.00){\line(1,0){6.00}}
	\put(100.00,15.00){\line(1,0){6.00}}
	\put(100.00,9.00){\line(1,0){6.00}}
	\put(100.00,3.00){\line(1,0){6.00}}
	\put(106.00,33.00){\line(0,-1){30.00}}
	\put(106.00,33.00){\line(1,0){6.00}}
	\put(106.00,27.00){\line(1,0){6.00}}
	\put(106.00,21.00){\line(1,0){6.00}}
	\put(106.00,15.00){\line(1,0){6.00}}
	\put(106.00,9.00){\line(1,0){6.00}}
	\put(106.00,3.00){\line(1,0){6.00}}
	\put(112.00,33.00){\line(0,-1){30.00}}
	\put(112.00,33.00){\line(1,0){6.00}}
	\put(112.00,27.00){\line(1,0){6.00}}
	\put(112.00,21.00){\line(1,0){6.00}}
	\put(112.00,15.00){\line(1,0){6.00}}
	\put(112.00,9.00){\line(1,0){6.00}}
	\put(112.00,3.00){\line(1,0){6.00}}
	\put(118.00,33.00){\line(0,-1){30.00}}
	\put(118.00,33.00){\line(1,0){6.00}}
	\put(118.00,27.00){\line(1,0){6.00}}
	\put(118.00,21.00){\line(1,0){6.00}}
	\put(118.00,15.00){\line(1,0){6.00}}
	\put(118.00,9.00){\line(1,0){6.00}}
	\put(118.00,3.00){\line(1,0){6.00}}
	\put(124.00,33.00){\line(0,-1){30.00}}
}

\put(56.00,0.00)
{
	\put(76.00,32.00){\line(0,-1){4.00}}
	\put(76.00,26.00){\line(0,-1){4.00}}
	\put(76.00,33.00){\circle{2.00}}
	\put(76.00,27.00){\circle{2.00}}
	\put(76.00,21.00){\circle{2.00}}
	\put(76.00,9.00){\circle{2.00}}
	\put(77.00,21.00){\line(1,0){4.00}}
	\put(77.00,9.00){\line(1,0){4.00}}
	\put(82.00,21.00){\circle{2.00}}
	\put(82.00,9.00){\circle{2.00}}
	\put(83.00,21.00){\line(1,0){4.00}}
	\put(83.00,9.00){\line(1,0){4.00}}
	\put(88.00,32.00){\line(0,-1){4.00}}
	\put(88.00,26.00){\line(0,-1){4.00}}
	\put(88.00,20.00){\line(0,-1){4.00}}
	\put(88.00,14.00){\line(0,-1){4.00}}
	\put(88.00,33.00){\circle{2.00}}
	\put(88.00,27.00){\circle{2.00}}
	\put(88.00,21.00){\circle{2.00}}
	\put(88.00,15.00){\circle{2.00}}
	\put(88.00,9.00){\circle{2.00}}
	\put(89.00,21.00){\line(1,0){4.00}}
	\put(89.00,9.00){\line(1,0){4.00}}
	\put(94.00,21.00){\circle{2.00}}
	\put(94.00,9.00){\circle{2.00}}
	\put(95.00,21.00){\line(1,0){4.00}}
	\put(100.00,32.00){\line(0,-1){4.00}}
	\put(100.00,26.00){\line(0,-1){4.00}}
	\put(100.00,33.00){\circle{2.00}}
	\put(100.00,27.00){\circle{2.00}}
	\put(100.00,21.00){\circle{2.00}}
	\put(101.00,33.00){\line(1,0){4.00}}
	\put(106.00,33.00){\circle{2.00}}
	\put(106.00,9.00){\circle{2.00}}
	\put(107.00,33.00){\line(1,0){4.00}}
	\put(107.00,9.00){\line(1,0){4.00}}
	\put(112.00,32.00){\line(0,-1){4.00}}
	\put(112.00,26.00){\line(0,-1){4.00}}
	\put(112.00,20.00){\line(0,-1){4.00}}
	\put(112.00,14.00){\line(0,-1){4.00}}
	\put(112.00,33.00){\circle{2.00}}
	\put(112.00,27.00){\circle{2.00}}
	\put(112.00,21.00){\circle{2.00}}
	\put(112.00,15.00){\circle{2.00}}
	\put(112.00,9.00){\circle{2.00}}
	\put(113.00,33.00){\line(1,0){4.00}}
	\put(113.00,9.00){\line(1,0){4.00}}
	\put(118.00,33.00){\circle{2.00}}
	\put(118.00,9.00){\circle{2.00}}
	\put(119.00,33.00){\line(1,0){4.00}}
	\put(119.00,9.00){\line(1,0){4.00}}
	\put(124.00,32.00){\line(0,-1){4.00}}
	\put(124.00,14.00){\line(0,-1){4.00}}
	\put(124.00,33.00){\circle{2.00}}
	\put(124.00,27.00){\circle{2.00}}
	\put(124.00,15.00){\circle{2.00}}
	\put(124.00,9.00){\circle{2.00}}
}
\end{picture}

\end{center}
\caption{Three representations~: conventional, matrix, induced subgraph.}

\bigskip

Our first goal is to give a handy characterization of those mappings $F$ that
correspond to the Hamiltonian circuits of $G_{m,n}^*$. For this purpose we
need a concept which allows us to represent the degree constraint of circuits.

Two vectors (or words) $u = u_1 \ldots u_p~,~ v = v_1 \ldots v_p \in
\{ 0,1 \}^p$ (for some $p$) are {\em compatible}, if for all 
$k~(1 \leq k < p)$
\[
{u_k ~~~~~ v_k \choose u_{k+1} ~ v_{k+1}} \not\in 
\left\{
{1 ~ 1 \choose 1 ~ 1} ,
{0 ~ 0 \choose 0 ~ 0} ,
{1 ~ 0 \choose 0 ~ 1} ,
{0 ~ 1 \choose 1 ~ 0}
\right\}
\]

Think of the matrix on the left as representing the ``inside''-``outside''
situation of four neighbouring cells of $G_{m,n}^*$ with respect to a 
Hamiltonian circuit $H^*$. 
It is clear that neither of the matrices on the r.h.s
is possible because they represent the situation at vertices of degree $0$ or
$4$ w.r.t. the subgraph $H^*$. Note that all the other 12 
$(2 \times 2)$-matrices over $\{ 0,1 \}$ may occur because 
they represent the situation occuring at vertices of degree $2$.

For any vector (word) $w \in \{0,1\}^m$ let $\overline{w}$ denote the
{\em augmented} vector $0 \cdot w \cdot 0 \in \{0,1\}^{m+2}$, constructed
by prepending and appending a $0$ to $w$.
Furthermore, let ${\bf 0} = 0^m \in \{ 0,1 \}^m$ denote the 
all-zero vector and ${\overline {\bf 0}} = 0^{m+2}$ 
the corresponding augmented vector.

It is easy to see, that the following holds:
\begin{itemize}
\item
if $H^*$ is a Hamiltonian circuit of $G_{m,n}^*$, then
\begin{itemize}
\item[--]
the sequence of vectors
\[
{\overline {\bf 0}}~,~ {\overline H}^{(1)}~,~ {\overline H}^{(2)}
~,~ \ldots ~,~{\overline H}^{(n)} ~,~ {\overline {\bf 0}}
\]
is a compatible sequence, i.e. ${\overline H}^{(i)}$ is compatible with
${\overline H}^{(i+1)}$ for $0 \leq i \leq n$, 
where we put ${\overline H}^{(0)} = {\overline {\bf 0}} 
= {\overline H}^{(n+1)}$ ;
\item[--]
the induced subgraph $H$ of $G_{m,n}$ is a tree.
\end{itemize}
\end{itemize} 

It is a little less obvious that the converse also holds: any mapping
$F \,:\, G_{m,n} \rightarrow \{ 0,1 \}$ such that the sequence
${\overline {\bf 0}} , {\overline F}^{(a)} , \ldots , {\overline F}^{(n)}, 
{\overline {\bf 0}}$ is compatible and such that $F$, 
viewed as an induced subgraph of $G_{m,n}$, is a tree, 
actually gives rise to a Hamiltonian circuit of $G_{m,n}^*$.
We give a short outline of {\em proof}:

$F$ will be used to define a subgraph $F^*$ of $G_{m,n}^*$ in the obvious way:

\begin{itemize}
\item
an edge $(x-1, y) \longleftrightarrow (x,y)$ , where
$1 \leq x \leq n ,\, 0 \leq y \leq m$ belongs to $F^*$ (together with its
endpoints) iff ${\overline F} (x,y) \not= {\overline F} (x,y + 1)$
\item
an edge $(x, y-1) \longleftrightarrow (x,y)$, where
$0 \leq x \leq n ,\, 1 \leq y \leq m$ belongs to $F^*$ iff
${\overline F} (x,y) \not= {\overline F} (x+1, y)$
\end{itemize}
We have used here the augmented $(m+2) \times (n+2)$-matrix ${\overline F}$:
\[
{\overline F} (x,y) =
\cases{
F(x,y)& if $ 1 \leq x \leq n, 1 \leq y \leq m$ \cr
0 & if $ x \in \{0, n+1 \}$ or $y \in \{0, m+1 \}$}
\]
is obtained by bordering $F$ with zeros.

The compatibility condition guarantees that $F^*$ has degree $2$ at each
vertex. The tree condition guarantees that $F^*$ is connected.


\section{Constructing Hamiltonian circuits}

Let us now consider the problem of systematically {\em constructing} 
Hamiltonian circuits $H^* \subseteq G_{m,n}^*$ for fixed $m$ and arbitrary
$n \in {\bf N}$. We have seen that these circuits correspond to mappings
$H : G_{m,n} \rightarrow \{ 0,1 \}$ such that the sequence 
${\overline {\bf 0}}, {\overline H}^{(1)} , {\overline H}^{(2)} , \ldots , 
{\overline H}^{(n)}, {\overline {\bf 0}}$ of augmented column vectors is a
compatible one, and that the induced subgraph $H \subseteq G_{m,n}$ is a
tree. This implies that each initial seqment 
${\overline {\bf 0}} , {\overline H}^{(1)}, \ldots , {\overline H}^{(k)}$ 
is a compatible sequence
and that the corresponding subgraph $H^{(1\ldots k)} \subseteq G_{m,k}$ is
a forest. This forest is ``special'' in that all its trees have at least
one vertex belonging to the last, the $k$-th column. We will now consider
two aspects: {\em continuation} and {\em termination}.

\begin{itemize}
\item
Continuation: if we want to extend such an initial segment in a way that
may ultimately lead to a Hamiltonian circuit $H^* \subseteq G_{m,n}^*$ for
some $n > k$, we have to examine as candidates for the $(k+1)$-st column
$H^{(k+1)}$ all nonzero vectors $K \in \{ 0,1 \}^m$ such that the following holds:
\begin{itemize}
\item
${\overline H}^{(k)}$ and ${\overline K}$ are compatible;

\item
the subgraph induced by $H^{(1)} , \ldots , H^{(k)} , K$ in
$G_{m,k+1}$ is again a special forest.
\end{itemize}

The first of these conditions can be easily checked by a finite automaton. 
What is less obvious is that for checking the second condition we do not need
to know the whole ``history'' $H^{(1)} , \ldots , H^{(k)}$, but only a limited (i.e.
bounded for $m$ fixed) amount of information in addition to knowing $H^{(k)}$ :
\begin{itemize}
\item[-]
we need to know which of the 1-cells of $H^{(k)}$
 (i.e. the $y$ such that $H^{(k)}_y = H(k,y) = 1$)
 belong to the same tree in the special forest
induced by $H^{(1)} , \ldots , H^{(k)}$.
\end{itemize}
We can then check whether the addition of $K$ as $(k+1)$-st column leads to
a cycle or not in the new induced subgraph, and if not, whether all the
previously existing trees are now merged into trees which all have at 
least one vertex belonging to in the $(k+1)$-st column. 
Note that the addition of $K$ may also create new
trees consisting of just a single vertex or a string of vertices in the
$(k+1)$-st column. (In the example given in Fig.~\ref{partition}, 
this happens in the third column.)

\item
Termination: If all the vertices of $H^{(k)}$ belong to the same tree, then
by maintaining the property of being a ``special'' forest by continuation, 
it is clear that the forest induced by $H^{(1)} , \ldots , H^{(k)}$ is in
fact a single tree. If ${\overline H}^{(k)}$ turns out to be compatible with
${\overline {\bf 0}}$, we may terminate the construction and a Hamiltonian
cycle of $G^*_{m,k}$ is constructed.
\end{itemize}


\section{Some technical details}

It should be evident from the previous section that for each fixed $m > 0$
a finite automaton can be constructed which works over the alphabet 
$\Sigma_m = \{ 0,1 \}^m$ and which accepts a word
$H = H^{(1)} H^{(2)} \ldots H^{(n)} \in \Sigma_m^*$ if and only if the
corresponding matrix $H$ represents a Hamiltonian circuit of $G_{m,n}^*$.
In this section we look a little closer on the problem how to construct
such an automaton. The main point is, of course, how to integrate the
knowledge about the forest induced by initial segments $H^{(1)} H^{(2)} 
\ldots H^{(k)}$ into the states of such an automaton.

Let us begin with recalling some familiar concepts from combinatorics. 
A {\em partition} of the set $[1..n] := \{ 1,2 , \ldots , n \}$ 
can be specified by a function $\pi : [1..n] \rightarrow [1..n]$
such that 
\[
\pi (1) = 1~,~ 
1 \leq \pi (j) \leq \max \{ \pi (i) ; i < j \} + 1 
~ \mbox{for} ~ 2 \leq j \leq n
\]
The idea of this coding is that element $j$ belongs to block number $k$ if
$\pi (j) = k$, and the sequence of smallest elements in blocks 
numbered $1,2,3, \ldots$ is increasing.

A partition $\pi$ of $[1..n]$ is {\em non-crossing} ($ncp$) 
if for each quadruple
$1 \leq i < j < k < l \leq n$
\[
\pi (i) = \pi (k) \wedge \pi (j) = \pi (l) ~~ \mbox{implies} ~~
\pi (i) = \pi (j) (= \pi (k) = \pi (l))
\]
For later use we introduce the notation ${\cal NCP}_n$ to denote the set
of non-crossing partitions of $[1..n]$.

If we look at the situation discussed above, namely that of a sequence
$H^{(1)}, H^{(2)}, \ldots , H^{(k)} ~ \mbox{in} ~ \Sigma_m$ inducing
 a ``special'' forest in $G_{m,k}$, we notice that the partition $\pi$ of
the vertices belonging to $H^{(k)}$ according to the membership in the trees
of the forest is necessarily an $ncp$. More precisely, let 
\[
{\overline H}^{(k)} = 0^{j_0} 1^{i_1} 0^{j_1} 1^{i_2} 
0^{j_2} \ldots 1^{i_r} 0^{j_r}~~\hbox{with}~~i_1, \ldots , i_r, j_0, j_1 , 
\ldots , j_r > 0
\]

\smallskip					%F3
						%F3
\setlength{\mylength}{\textwidth}		%F3
\addtolength{\mylength}{-3.0cm}			%F3
						%F3
\noindent					%F3
\begin{minipage}{\mylength}			%F3
be the unique factorization of ${\overline H}^{(k)}$ into
maximal $0$-blocks and maximal $1$-blocks. Vertices belonging to the same
$1$-block obviously belong to the same tree induced by $H^{(1)} , \ldots ,
H^{(k)}$. Thus a partition $\pi$ of $[1..r]$ indicates to which
tree the vertices of each $1$-block belong. 
An example is given in
Fig.~\ref{partition}, where a Hamiltonian circuit on $G_{9,5}^*$, 
written in matrix form,
is given, together with the {\em ncp}s associated to the five column vectors
and coding the backward tree structure.
These partitions $\pi$ must belong to 
${\cal NCP}$ for obvious topological reasons. 
Otherwise we would have a contradictory situation as 
indicated in Fig.~\ref{cross}.

These objects, pairs $(u,\pi)$ consisting of a vector 
$u \in \{ 0,1 \}^m$ together with an $ncp ~ \pi$ on its 
set of maximal $1$-blocks, 
are actually the {\em  states} of the automaton we are
going to construct. 
\end{minipage}
\hfill					%F3
\begin{minipage}{2.0cm}				%F3
 \begin{center}					%F3
  \unitlength=0.7pt
\begin{picture}(60.70,261.09)(8.50,8.45)
\put(55.51,8.45){\line(0,1){17.01}}
\put(38.41,8.45){\line(0,1){17.01}}
\put(55.51,25.46){\line(0,1){17.01}}
\put(38.41,25.46){\line(0,1){17.01}}
\put(55.51,42.47){\line(0,1){17.01}}
\put(38.47,25.50){\line(1,0){17.01}}
\put(55.49,8.41){\line(-1,0){17.01}}
\put(38.47,59.50){\line(0,-1){17.00}}
\put(38.47,42.50){\line(1,0){17.01}}
\put(38.40,59.50){\line(1,0){17.01}}
\put(55.51,78.45){\line(0,1){17.01}}
\put(38.41,78.45){\line(0,1){17.01}}
\put(55.51,95.46){\line(0,1){17.01}}
\put(38.41,95.46){\line(0,1){17.01}}
\put(55.51,112.47){\line(0,1){17.01}}
\put(38.47,95.50){\line(1,0){17.01}}
\put(55.49,78.41){\line(-1,0){17.01}}
\put(38.47,129.50){\line(0,-1){17.00}}
\put(38.47,112.50){\line(1,0){17.01}}
\put(38.40,129.50){\line(1,0){17.01}}
\put(55.51,148.45){\line(0,1){17.01}}
\put(38.41,148.45){\line(0,1){17.01}}
\put(55.51,165.46){\line(0,1){17.01}}
\put(38.41,165.46){\line(0,1){17.01}}
\put(55.51,182.47){\line(0,1){17.01}}
\put(38.47,165.50){\line(1,0){17.01}}
\put(55.49,148.41){\line(-1,0){17.01}}
\put(38.47,199.50){\line(0,-1){17.00}}
\put(38.47,182.50){\line(1,0){17.01}}
\put(38.40,199.50){\line(1,0){17.01}}
\put(55.51,218.45){\line(0,1){17.01}}
\put(38.41,218.45){\line(0,1){17.01}}
\put(55.51,235.46){\line(0,1){17.01}}
\put(38.41,235.46){\line(0,1){17.01}}
\put(55.51,252.47){\line(0,1){17.01}}
\put(38.47,235.50){\line(1,0){17.01}}
\put(55.49,218.41){\line(-1,0){17.01}}
\put(38.47,269.50){\line(0,-1){17.00}}
\put(38.47,252.50){\line(1,0){17.01}}
\put(38.40,269.50){\line(1,0){17.01}}
\put(38.00,244.00){\line(-2,-5){28.00}}
\put(38.07,103.32){\line(-2,5){28.07}}
\put(38.00,175.00){\line(-2,-5){29.00}}
\put(37.96,31.16){\line(-2,5){28.96}}
\put(7.84,139.85){\vector(1,0){10.23}}
\put(23.47,139.85){\circle{8}}
\put(47.01,16.96){\makebox(0,0)[cc]{1}}
\put(47.01,50.97){\makebox(0,0)[cc]{1}}
\put(47.06,38.04){\makebox(0,0)[cc]{\vdots}}
\put(47.01,86.96){\makebox(0,0)[cc]{1}}
\put(47.01,120.97){\makebox(0,0)[cc]{1}}
\put(47.06,108.04){\makebox(0,0)[cc]{\vdots}}
\put(47.01,156.96){\makebox(0,0)[cc]{1}}
\put(47.01,190.97){\makebox(0,0)[cc]{1}}
\put(47.06,178.04){\makebox(0,0)[cc]{\vdots}}
\put(47.01,226.96){\makebox(0,0)[cc]{1}}
\put(47.01,260.97){\makebox(0,0)[cc]{1}}
\put(47.06,248.04){\makebox(0,0)[cc]{\vdots}}
\put(68.53,243.91){\makebox(0,0)[cc]{A}}
\put(68.43,173.58){\makebox(0,0)[cc]{B}}
\put(68.43,103.85){\makebox(0,0)[cc]{A}}
\put(68.43,33.60){\makebox(0,0)[cc]{B}}
\end{picture}
				%F3
  \caption{}\label{cross}			%F3
 \end{center}					%F3
\end{minipage}					%F3
						%F3
\smallskip					%F3
 
\noindent
\begin{center}
 \begin{minipage}{290pt}
  \begin{minipage}{95pt}
   \begin{center}
    \unitlength=0.7pt
\begin{picture}(104.45,153.09)(8.50,8.45)
\put(93.56,8.45){\line(-1,0){85.05}}
\put(93.56,8.45){\line(0,1){17.01}}
\put(76.54,8.45){\line(0,1){17.01}}
\put(59.53,8.45){\line(0,1){17.01}}
\put(42.53,8.45){\line(0,1){17.01}}
\put(25.51,8.45){\line(0,1){17.01}}
\put(8.51,8.45){\line(0,1){17.01}}
\put(93.56,25.46){\line(-1,0){85.05}}
\put(93.56,25.46){\line(0,1){17.01}}
\put(76.54,25.46){\line(0,1){17.01}}
\put(59.53,25.46){\line(0,1){17.01}}
\put(42.53,25.46){\line(0,1){17.01}}
\put(25.51,25.46){\line(0,1){17.01}}
\put(8.51,25.46){\line(0,1){17.01}}
\put(93.56,42.47){\line(-1,0){85.05}}
\put(93.56,42.47){\line(0,1){17.01}}
\put(76.54,42.47){\line(0,1){17.01}}
\put(59.53,42.47){\line(0,1){17.01}}
\put(42.53,42.47){\line(0,1){17.01}}
\put(25.51,42.47){\line(0,1){17.01}}
\put(8.51,42.47){\line(0,1){17.01}}
\put(93.56,59.48){\line(-1,0){85.05}}
\put(93.56,59.48){\line(0,1){17.01}}
\put(76.54,59.48){\line(0,1){17.01}}
\put(59.53,59.48){\line(0,1){17.01}}
\put(42.53,59.48){\line(0,1){17.01}}
\put(25.51,59.48){\line(0,1){17.01}}
\put(8.51,59.48){\line(0,1){17.01}}
\put(93.56,76.49){\line(-1,0){85.05}}
\put(93.56,76.49){\line(0,1){17.01}}
\put(76.54,76.49){\line(0,1){17.01}}
\put(59.53,76.49){\line(0,1){17.01}}
\put(42.53,76.49){\line(0,1){17.01}}
\put(25.51,76.49){\line(0,1){17.01}}
\put(8.51,76.49){\line(0,1){17.01}}
\put(93.56,93.50){\line(-1,0){85.05}}
\put(93.56,93.50){\line(0,1){17.01}}
\put(76.54,93.50){\line(0,1){17.01}}
\put(59.53,93.50){\line(0,1){17.01}}
\put(42.53,93.50){\line(0,1){17.01}}
\put(25.51,93.50){\line(0,1){17.01}}
\put(8.51,93.50){\line(0,1){17.01}}
\put(93.56,110.51){\line(-1,0){85.05}}
\put(93.56,110.51){\line(0,1){17.01}}
\put(76.54,110.51){\line(0,1){17.01}}
\put(59.53,110.51){\line(0,1){17.01}}
\put(42.53,110.51){\line(0,1){17.01}}
\put(25.51,110.51){\line(0,1){17.01}}
\put(8.51,110.51){\line(0,1){17.01}}
\put(93.56,127.52){\line(-1,0){85.05}}
\put(93.56,127.52){\line(0,1){17.01}}
\put(76.54,127.52){\line(0,1){17.01}}
\put(59.53,127.52){\line(0,1){17.01}}
\put(42.53,127.52){\line(0,1){17.01}}
\put(25.51,127.52){\line(0,1){17.01}}
\put(8.51,127.52){\line(0,1){17.01}}
\put(93.56,144.53){\line(-1,0){85.05}}
\put(93.56,144.53){\line(0,1){17.01}}
\put(76.54,144.53){\line(0,1){17.01}}
\put(59.53,144.53){\line(0,1){17.01}}
\put(42.53,144.53){\line(0,1){17.01}}
\put(25.51,144.53){\line(0,1){17.01}}
\put(8.51,144.53){\line(0,1){17.01}}
\put(93.56,161.54){\line(-1,0){85.05}}
\put(17.01,16.96){\makebox(0,0)[cc]{1}}
\put(34.02,16.96){\makebox(0,0)[cc]{1}}
\put(51.03,16.96){\makebox(0,0)[cc]{1}}
\put(68.04,16.96){\makebox(0,0)[cc]{1}}
\put(85.05,16.96){\makebox(0,0)[cc]{1}}
\put(17.01,33.96){\makebox(0,0)[cc]{0}}
\put(34.02,33.96){\makebox(0,0)[cc]{0}}
\put(51.03,33.96){\makebox(0,0)[cc]{1}}
\put(68.04,33.96){\makebox(0,0)[cc]{0}}
\put(85.05,33.96){\makebox(0,0)[cc]{0}}
\put(17.01,50.97){\makebox(0,0)[cc]{1}}
\put(34.02,50.97){\makebox(0,0)[cc]{1}}
\put(51.03,50.97){\makebox(0,0)[cc]{1}}
\put(68.04,50.97){\makebox(0,0)[cc]{1}}
\put(85.05,50.97){\makebox(0,0)[cc]{1}}
\put(17.01,67.98){\makebox(0,0)[cc]{0}}
\put(34.02,67.98){\makebox(0,0)[cc]{0}}
\put(51.03,67.98){\makebox(0,0)[cc]{1}}
\put(68.04,67.98){\makebox(0,0)[cc]{0}}
\put(85.05,67.98){\makebox(0,0)[cc]{1}}
\put(17.01,84.99){\makebox(0,0)[cc]{1}}
\put(34.02,84.99){\makebox(0,0)[cc]{1}}
\put(51.03,84.99){\makebox(0,0)[cc]{1}}
\put(68.04,84.99){\makebox(0,0)[cc]{0}}
\put(85.05,84.99){\makebox(0,0)[cc]{1}}
\put(17.01,102.01){\makebox(0,0)[cc]{1}}
\put(34.02,102.01){\makebox(0,0)[cc]{0}}
\put(51.03,102.01){\makebox(0,0)[cc]{0}}
\put(68.04,102.01){\makebox(0,0)[cc]{0}}
\put(85.05,102.01){\makebox(0,0)[cc]{1}}
\put(17.01,119.02){\makebox(0,0)[cc]{1}}
\put(34.02,119.02){\makebox(0,0)[cc]{0}}
\put(51.03,119.02){\makebox(0,0)[cc]{1}}
\put(68.04,119.02){\makebox(0,0)[cc]{1}}
\put(85.05,119.02){\makebox(0,0)[cc]{1}}
\put(17.01,136.03){\makebox(0,0)[cc]{1}}
\put(34.02,136.03){\makebox(0,0)[cc]{0}}
\put(51.03,136.03){\makebox(0,0)[cc]{0}}
\put(68.04,136.03){\makebox(0,0)[cc]{0}}
\put(85.05,136.03){\makebox(0,0)[cc]{1}}
\put(17.01,153.04){\makebox(0,0)[cc]{1}}
\put(34.02,153.04){\makebox(0,0)[cc]{1}}
\put(51.03,153.04){\makebox(0,0)[cc]{1}}
\put(68.04,153.04){\makebox(0,0)[cc]{0}}
\put(85.05,153.04){\makebox(0,0)[cc]{1}}
\put(112.96,85.23){\makebox(0,0)[cc]{{\boldmath $\rightarrow$}}}
\end{picture}
 
   \end{center}
  \end{minipage}
  \begin{minipage}{190pt}
   $
    \left(
     \begin{array}{c}
      1\\
      2\\
      3
     \end{array}
    \right)
    ,
    \left(
     \begin{array}{c}
      1\\
      1\\
      2\\
      3
     \end{array}
    \right)
    ,
    \left(
     \begin{array}{c}
      1\\
      2\\
      1
     \end{array}
    \right)
    ,
    \left(
     \begin{array}{c}
      1\\
      2\\
      2
     \end{array}
    \right)
    ,
    \left(
     \begin{array}{c}
      1\\
      1
     \end{array}
    \right)
   $
  \end{minipage}
 \end{minipage}
\end{center}

\smallskip

\noindent
\caption{Example~: The partitions $\pi$ corresponding to the columns.}
\label{partition}

\vskip0.5cm

We now define the state set:
\[
Q_m = \left\{\, q = (u, \pi) \,;\,
u \in \{ 0,1 \}^m ,
\pi ~ ncp ~\mbox{on maximal 1-blocks of} ~ u \,\right\}
\]


\section{Construction of the automaton ${\cal A}_m$}

Let
$ L_{m} \subset \Sigma_m^*$
denote the set of matrices corresponding to Hamiltonian circuits on
$G_{m,n}^*$ for some $n \geq 1$.
$L_m$ will be considered as a
language over the alphabet $\Sigma_m = \{0,1\}^m$, written as column
vectors, and with horizontal concatenation of columns as operation. 
In this section we will construct
a finite automaton ${\cal A}_{m}$ recognizing this language $L_m$.

\begin{center}
 \unitlength=0.7pt
%\unitlength=1.0pt
\begin{picture}(400.63,290)(0,-80)
\newsavebox{\state}
\savebox{\state}(00.00,50.00)
{
	\put(25.36,25.36){\line(-1,0){17.01}}
	\put(8.35,42.37){\line(1,0){17.01}}
	\put(8.35,8.35){\framebox(17.01,51.03)[cc]{}}
	\put(24.51,34.26){\oval(50.63,66.64)}
}
%\put(00.00,-5.00){\put(24.51,34.26){\oval(50.63,66.64)}}
\put(0,0)
{
	\usebox{\state}
	\put(16.85,45.88){\makebox(0,0)[cc]{0}}
	\put(16.90,28.77){\makebox(0,0)[cc]{1}}
	\put(16.80,11.77){\makebox(0,0)[cc]{0}}
	\put(38.00,28.00){\makebox(0,0)[cc]{$\left(1\right)$}}
}
%\put(200.00,-5.00){\put(24.51,34.26){\oval(50.63,66.64)}}
\put(200.00,0)
{
	\usebox{\state}
	\put(16.85,45.88){\makebox(0,0)[cc]{0}}
	\put(16.90,28.77){\makebox(0,0)[cc]{0}}
	\put(16.80,11.77){\makebox(0,0)[cc]{1}}
	\put(38.00,28.00){\makebox(0,0)[cc]{$\left(1\right)$}}
}
%\put(280.00,5.00){\put(24.51,34.26){\oval(50.63,66.64)}}
\put(280.00,10.00)
{
	\usebox{\state}
	\put(16.85,45.88){\makebox(0,0)[cc]{1}}
	\put(16.90,28.77){\makebox(0,0)[cc]{0}}
	\put(16.80,11.77){\makebox(0,0)[cc]{1}}
	\put(32.80,30.07)
	{
		\makebox(0,0)[cc]
		{
		  $
		   \left(\!\!\!\!\hspace{1.0pt}
		    \begin{array}{c}
		     1\\
		     1
		    \end{array}
		   \hspace{1.0pt}\!\!\!\!\right)
		  $
		}
	}
}
%\put(50.00,65.00){\put(24.51,34.26){\oval(50.63,66.64)}}
\put(55.00,70.00){\usebox{\state}
	\put(16.85,45.88){\makebox(0,0)[cc]{1}}
	\put(16.90,28.77){\makebox(0,0)[cc]{0}}
	\put(16.80,11.77){\makebox(0,0)[cc]{1}}
	\put(32.80,30.07){
		\makebox(0,0)[cc]{
		  $
		   \left(\!\!\!\!\hspace{1.0pt}
		    \begin{array}{c}
		     1\\
		     2
		    \end{array}
		   \hspace{1.0pt}\!\!\!\!\right)
		  $
		                 }
		         }
           }
%\put(135.00,55.00){\put(24.51,34.26){\oval(50.63,66.64)}}
\put(135.00,60.00)
{
	\usebox{\state}
	\put(16.85,45.88){\makebox(0,0)[cc]{1}}
	\put(16.90,28.77){\makebox(0,0)[cc]{1}}
	\put(16.80,11.77){\makebox(0,0)[cc]{1}}
	\put(38.00,28.00){\makebox(0,0)[cc]{$\left(1\right)$}}
}
%\put(350.00,65.00){\put(24.51,34.26){\oval(50.63,66.64)}}
\put(350.00,70.00)
{	
	\usebox{\state}
	\put(16.85,45.88){\makebox(0,0)[cc]{1}}
	\put(16.90,28.77){\makebox(0,0)[cc]{0}}
	\put(16.80,11.77){\makebox(0,0)[cc]{0}}
	\put(38.00,28.00){\makebox(0,0)[cc]{$\left(1\right)$}}
}
%\put(250.00,185.00)
%{
%	\put(-24.51,-34.26)
%	{
%		\usebox{\state}
%		\put(16.85,45.88){\makebox(0,0)[cc]{0}}
%		\put(16.90,28.77){\makebox(0,0)[cc]{0}}
%		\put(16.80,11.77){\makebox(0,0)[cc]{0}}
%		\put(38.00,28.00){\makebox(0,0)[cc]{$\left(\right)$}}
%		\put(38.00,50.00){\makebox(0,0)[cc]{$\omega$}}
%	}
%}
%Hier gehts weiter einer der neuen ovale wurde schon eingef"ugt (siehe oben)
%so.
\put(159.51,185.00)
{
	\put(-24.51,-34.26)
	{
		\usebox{\state}
		\put(16.85,45.88){\makebox(0,0)[cc]{0}}
		\put(16.90,28.77){\makebox(0,0)[cc]{0}}
		\put(16.80,11.77){\makebox(0,0)[cc]{0}}
		\put(38.00,28.00){\makebox(0,0)[cc]{$\left(\right)$}}
%		\put(38.00,50.00){\makebox(0,0)[cc]{$\alpha$}}
	}
}
\put(5,-20.00)
{
%	\put(353.07,147.84){\vector(-1,0){257.07}}
%	\put(74.74,174.07){\vector(0,-1){19.13}}
%	\put(159.39,174.34){\vector(0,-1){29.38}}
%	\put(102.13,119.97){\vector(1,0){29.79}}
%	\put(196.82,40.09){\vector(-2,1){100.91}}
%	\put(52.28,58.07){\vector(2,1){79.65}}
%	\put(137.92,80.52){\vector(-2,-1){86.01}}
%	\put(186.95,120.53){\vector(1,0){159.94}}
%	\put(347.01,134.77){\vector(-1,0){163.70}}
%	\put(186.86,105.09){\vector(4,-1){92.41}}
%	\put(185.47,88.20){\vector(3,-1){21.44}}
%	\put(196.74,61.67){\vector(-2,1){25.86}}
%	\put(276.91,48.83){\vector(-1,0){24.78}}
%	\put(329.70,82.54){\vector(3,2){19.86}}
%	\put(304.74,24.02){\vector(0,-1){22.63}}
%	\put(159.91,74.02){\vector(0,-1){72.72}}


%\put(24.51,49.26){\oval(50.63,66.64)}
%\put(224.51,49.26){\oval(50.63,66.64)}
%\put(304.51,59.26){\oval(50.63,66.64)}
%\put(74.51,119.26){\oval(50.63,66.64)}
%\put(159.51,109.26){\oval(50.63,66.64)}
%\put(374.51,119.26){\oval(50.63,66.64)}
%\put(250.00,200.00){\oval(50.63,66.64)}
%\put(159.51,200.00){\oval(50.63,66.64)}
	\put(46.50,118.50){\oval(51.00,25.00)[l]}
	\put(46.00,131.00){\vector(1,0){1.00}}
	\put(332.00,58.50){\oval(52.00,25.00)[r]}
	\put(333.00,46.00){\vector(-1,0){1.00}}
	\put(353.07,147.84){\vector(-1,0){257.07}}
	\put(132.67,180.48){\vector(-2,-1){50.02}}
	\put(155.00,160.00){\vector(0,-1){15.00}}
	\put(165.00,145.00){\vector(0,1){15.00}}
	\put(102.13,119.97){\vector(1,0){29.79}}
	\put(196.82,40.09){\vector(-2,1){100.91}}
	\put(52.28,58.07){\vector(2,1){79.65}}
	\put(137.92,80.52){\vector(-2,-1){86.01}}
	\put(186.95,120.53){\vector(1,0){159.94}}
	\put(347.01,134.77){\vector(-1,0){163.70}}
	\put(186.86,105.09){\vector(4,-1){92.41}}
	\put(185.47,88.20){\vector(3,-1){21.44}}
	\put(196.74,61.67){\vector(-2,1){25.86}}
	\put(276.91,48.83){\vector(-1,0){24.78}}
	\put(329.70,82.54){\vector(3,2){19.86}}
	\put(46.00,131.00){\vector(1,0){1.00}}
	\put(333.00,46.00){\vector(-1,0){1.00}}
%	\put(174.59,142.84){\vector(3,2){49.90}}
%	\put(291.12,93.59){\vector(-1,2){35.11}}
        \put(280,85){\vector(-1,1){95}}
}
\put(60,-80)
{       \usebox{\state}
        \put(16.85,45.88){\makebox(0,0)[cc]{1}}
	\put(16.90,28.77){\makebox(0,0)[cc]{1}}
	\put(16.80,11.77){\makebox(0,0)[cc]{0}}
	\put(38.00,28.00){\makebox(0,0)[cc]{$\left(1\right)$}}
}
\put(240,-80)
{       \usebox{\state}
        \put(16.85,45.88){\makebox(0,0)[cc]{0}}
	\put(16.90,28.77){\makebox(0,0)[cc]{1}}
	\put(16.80,11.77){\makebox(0,0)[cc]{1}}
	\put(38.00,28.00){\makebox(0,0)[cc]{$\left(1\right)$}}
}
\put(120,-60){\vector(1,0){120}}
\put(240,-50){\vector(-1,0){120}}
\end{picture}

\end{center}
\caption{The transition system ${\cal T}_{3}$}\label{auto}

\bigskip

We first construct a transition system ${\cal T}_m = (Q_m, \rightarrow)$ as follows:
\begin{quote}
for $q, q' \in Q_m$ with $q = (u, \pi )$, $q' = (v, \sigma)$ we put
$q \rightarrow q'$ if and only if the following holds
\begin{itemize}
\item[--]
${\overline u}$ and ${\overline v} \in \{ 0,1 \}^{m+2}$ are compatible vectors
\item[--]
extending the (type of) special forest structure encoded in $q=(u,\pi)$ 
via the {\em ncp} $\pi$ by column $v$ again leads to a (type of) special forest 
structure, which is encoded by $(v,\sigma)$.
\end{itemize}
\end{quote}

It must be admitted that checking the second item is rather intricate
to implement. No further details are given here, see \cite{stoyan}. 
We point out, however, that given a state
$q = (u, \pi)$ and $v \in \Sigma_m$ such that ${\overline u}$ and ${\overline v}$ are
compatible, there is {\em at most one} $\sigma$ such that $q' = (v, \sigma)
\in Q_m$ and $q \rightarrow q'$ holds. The paths of length $n+1$ in ${\cal T}_m$, 
starting at $q_0 :=({\bf 0},\emptyset)$ and ending in $q_0$, 
without returning to $q_0$ in between, precisely correspond to the 
Hamiltonian circuits of $G_{m,n}^*$. 

This leads to the construction of the automaton
${\cal A}_m := \langle Q'_m, \Sigma_m, \delta, \alpha, \Omega\rangle$. 
Again, we take
$\Sigma_m = \{ 0,1 \}^m$ as alphabet and define a 
{\em complete deterministic} automaton over the state set
\[
Q'_m = \left\{ Q_m \setminus q_0 \right\}
\cup
\left\{ \alpha, \rho \right\}
\]
where the new states $\alpha$ ($\rho$ resp.) serve as {\em initial}
({\em dead} resp.) states. The set $\Omega$ of terminal states is given by
\[
\Omega = 
\{\,(u,\pi_{\omega})\,;\,
(u,\pi_{\omega}) \rightarrow q_0~\hbox{in}~{\cal T}_m\,\}
\]
Here $\pi_{\omega} = (1)$ denotes the {\em ncp} where all 1-blocks
belong to the same class.

The transition function
$\delta ~:~Q_m' \times \Sigma_m \rightarrow Q_m'$ is defined as follows:
\begin{itemize}
\item[--]
for $q=(u,\pi) , \, q' = (v,\sigma) \in Q_m \setminus \{q_0\}$ :
\[
\delta(q,v) := 
\cases{
q' & iff $q \rightarrow q' ~\hbox{in}~{\cal T}_m$ \cr
\rho & iff $q \not\rightarrow q' ~\hbox{in}~{\cal T}_m$}
\]
\item[--]
for each $u \in \Sigma_m$  such that 
$q_0 \rightarrow (u,\pi_{\alpha})~\hbox{in}~{\cal T}_m$ :
\[
\delta(\alpha,u) = (u,\pi_{\alpha})
\]
\end{itemize}
Here $\pi_{\alpha}$ is the {\em ncp} where each 1-block 
of $u$ is in a class by itself.

The language $L_m$ of Hamiltonian circuits on $G_{m,n}^*$ 
(for some $n \geq 1$) is the language accepted by ${\cal A}_m$.
In particular, we have thus shown that the language $L_m$ is
a regular (rational) language for any $m$, and that its 
generating function is rational.

\section{A review of the Motzkin language}

In the next section we will present another way of writing the states
of our transition systems ${\cal T}_m$, hence of the automata ${\cal A}_m$.
This has the double advantage of being closer to the actual implementation
of the automata, and of giving precise information about the size (number
of states) of ${\cal T}_m$ and ${\cal A}_m$. Quite surprisingly, it turns out
that the states of ${\cal T}_m$ can be put into bijection with the words 
of length $m+1$ of the familiar Motzkin language.

In the present section we recall some (familiar) facts about the
Motzkin language ${\cal M}$ over the ternary alphabet $\{x,\xbar,y\}$.
This language can be defined as the unique solution in $\{x,\xbar,y\}^*$
of the fixed point equation
\[
Z = y^* \cdot ( \lambda + x \cdot Z \cdot \xbar \cdot Z)~~~,
\]
where $\lambda$ denotes the empty word. This equation reflects the fact that
${\cal M}$ is a context-free language, generated by the (unambiguous)
grammar
\[
Z \rightarrow Y + Y \cdot x \cdot Z \cdot \xbar \cdot Z~~,~~
Y \rightarrow \lambda + y \cdot Y
\]
Hence, a word $w \in \{x,\xbar,y\}^*$ belongs to ${\cal M}$ if and only if
one of the two cases holds:
\begin{itemize}
\item[--]
$w = y^k$ for some $k \geq 0$
\item[--]
$w$ has a factorization $w = y^k \cdot x \cdot u \cdot \xbar \cdot v$
with $u,v \in {\cal M}$ and $k \geq 0$ (recursion!)
\end{itemize}

Another way of looking at the Motzkin language is by taking the Dyck language 
over the alphabet $\{x,\xbar\}$ and ``shuffling'' it with the set of words
$y^* = \{ y^k\,;\, k \geq 0 \}$.

We note in passing that the set ${\cal NCP}_n$ of non-crossing partitions of 
$[1..n]$ is in bijection with the words of length $2n$ of the Dyck-language
over $\{x,\xbar\}$, hence the cardinality $\sharp {\cal NCP}_n$ is
the Catalan number $\hbox{\em cat}_n = {1 \over n+1}{2n \choose n}$.

We now list some known facts about 
$\hbox{\em mot}_n := \sharp {\cal M}_n$, the number of
Motzkin words of length $n$:
\begin{itemize}
\item[--]
The sum representation
\[
\hbox{\em mot}_n = 
\sum_{k=0}^{\lfloor n/2 \rfloor} \hbox{\em cat}_k {n \choose 2 k}
= \sum_{k=0}^{\lfloor n/2 \rfloor} {1 \over k+1} {2k \choose k}{n \choose 2k}
\]
\item[--]
The generating function
\begin{eqnarray*}
\sum_n \hbox{\em mot}_n \, z^n &=&
\frac{1-z-\sqrt{1-2z-3z^2}}{2z^2} \\
&=&
1+z+2 z^2+4 z^3 + 9 z^4 + 21 z^5 + 51 z^6 + \ldots
\end{eqnarray*}
\item[--]
The asymptotic behaviour
\[
\hbox{\em mot}_n =
\sqrt{3 \over 4\,\pi\,n^3} \, 3^n - 
{45 \over 32} {1 \over \sqrt{3 \,\pi\,n^5}}
\, 3^n + O\left({3^n \over n^{7/2}}\right)
\]
\end{itemize}


\section{A bijection}

We will now define a mapping $\Psi$ which maps the state set
$Q_m$ of the transition system ${\cal T}_m$ bijectively onto
the set ${\cal M}_{m+1}$ of words of length $m+1$ of the
Motzkin language ${\cal M}$ over the alphabet $\{x,\xbar,y\}$.

The definition is by induction on $m$.

\begin{itemize}
\item[--]
For $m=0$, we formally introduce $Q_0 = \{(\lambda,\emptyset)\}$,
where $\lambda$ is the empty word and $\emptyset$ denotes the empty
partition, the unique element of ${\cal NCP}_0$. This ``state''
is mapped by $\Psi$ onto the word $y \in {\cal M}_1$.

\item[--]
More generally: for any $m \geq 0$, the state set $Q_m$ contains the element
$(0^m,\emptyset)$, and this particular state will be mapped by $\Psi$
onto the word $y^{m+1} \in {\cal M}_{m+1}$.

\item[--]
Let $q = (u,\pi) \in Q_m, q \neq (0^m,\emptyset)$. Then $u \in \{0,1\}^m$ has
$r$ maximal 1-blocks for some $r$ with $1 \leq r \leq \lfloor m/2 \rfloor$, and
$\pi$ is an element of ${\cal NCP}_r$. As in Section 4, write
\[
\overline{u} = 0 \cdot u \cdot 0 = 
0^{j_0} 1^{i_1} 0^{j_1} 1^{i_2} 0^{j_2} \ldots 1^{i_r} 0^{j_r}
\]
with $i_1, \ldots ,i_r,j_0, \ldots ,j_r > 0$ and
\[
i_1 + \ldots + i_r + j_0 +\ldots + j_r = m+2
\]
Now factorize $\pi$ according to the last position in 
$\pi(1) \pi(2) \ldots \pi(r)$ where ``1'' appears. Let
\begin{eqnarray*}
k &=& \max \{\,\nu\,;\, \pi(\nu) = 1 \,\} \\
h &=& \max \{\,\pi(\nu)\,;\,1 \leq \nu \leq k \,\}
\end {eqnarray*}
Thus $k$ is this last position and $h$ is the maximum block number that appears
up to this position. By the properties of non-crossing partitions it is clear that
after position $k$ only block numbers bigger than $h$ appear in $\pi$.
More precisely:
\begin{eqnarray*}
\pi' &:=&
\pi(1) \pi(2) \ldots \pi(k-1) \in {\cal NCP}_{k-1} \\
\pi'' &:=&
(\pi(k+1)-h)(\pi(k+2)-h) \ldots(\pi(r)-h) \in {\cal NCP}_{r-k}
\end{eqnarray*}
(This decomposition $\pi \mapsto (\pi',\pi'')$ can actually be used to
produce a bijection between ${\cal NCP}_r$ and the set of Dyck words of length $2r$.)

Now let
\begin{eqnarray*}
q' &:=&
\left(
0^{j_0} 1^{i_1} 0^{j_1} \ldots 0^{j_{k-2}} 1^{i_{k-1}} 0^{j_{k-1}}\,,\,\pi' 
\right) 
\in Q_{m'} \\
q'' &:=&
\left(
0^{j_k} 1^{i_{k+1}} 0^{j_{k+1}} \ldots 0^{j_{r-1}} 1^{i_r} 0^{j_r}\,,\,\pi''
\right)
\in Q_{m''} \end{eqnarray*}
where
\begin{eqnarray*}
i_1 + \cdots + i_{k-1} + j_0 + \cdots + j_{k-1}  & = & m'+2 \\
i_{k+1} + \cdots + i_r + j_k + \cdots + j_r &=& m''+2
\end{eqnarray*}
and define
\[
\Psi(q) := y^{i_k-1} \cdot x \cdot \Psi(q') \cdot \xbar \cdot \Psi(q'')
\]
If we assume (by induction) that 
\[
\Psi(q') \in {\cal M}_{m'+1}~~~\hbox{and}~~~
\Psi(q'') \in {\cal M}_{m''+1}
\]
then --- in view of the characterization on ${\cal M}$ given in the previous 
section --- we have
\[
\Psi(q) \in {\cal M}_t
~~~\hbox{where}~~~
t = i_k + 1 + m'+1 + m''+1 = m+1~~,
\]
as desired. It is a routine task to check that this decomposition
and the mapping $\Psi$ can be perfectly reversed,
i.e. $\Psi$ maps $Q_m$ bijectively onto ${\cal M}_{m+1}$ for each $m \geq 0$.
\end{itemize}

Let us illustrate this construction of $\Psi$ by an example.
For this purpose we take states $q = (u, \pi) \in Q_m$ with $u$ as above
and write it as
\[
q \equiv
0^{j_0} \pi(1)^{i_1} 0^{j_1} \pi(2)^{i_2} 0^{j_2} \ldots \pi(r)^{i_r} 0^{j_r}
\]
i.e. we replace the ones in the 1-blocks of $\overline{u} = 0 \cdot u \cdot 0$
by the corresponding $\pi$-values of the blocks. We let $\Psi$ operate
on words of this type. (Note that in this coding we have $\Psi(0^n) = y^{n-1}$
for $n>0$.)

Let $m=30$ and $q=(u,\pi)$ with
\[
u = 
0^1 1^2 0^3 1^1 0^2 1^3 0^1 1^4 0^2 1^1 0^1 1^2 0^2 1^1 0^3 1^1 \in \{0,1\}^{30}
\] 
and
\[
\pi = 1\,2\,1\,1\,3\,4\,3\,5 \in {\cal NCP}_8
\]
We have
\[
k=4~,~
h=2 ~,~
i_k=4 ~,~
\pi' = 1\,2\,1~,~ \pi'' = 1\,2\,1\,3
\]
so that
\[
q \equiv
0^2 1^2 0^3 2^1 0^2 1^3 0^1 1^4 0^2 3^1 0^1 4^2 0^2 3^1 0^3 5^1 0^1
\]
will be mapped onto
\[
\Psi(q) =
y^3 \cdot x \cdot 
\Psi(0^2 1^2 0^3 2^1 0^2 1^3 0^1) \cdot \xbar \cdot
\Psi(0^2 1^1 0^1 2^2 0^2 1^1 0^3 3^1 0^1)
\]
Proceeding inductively we arrive at
\begin{eqnarray*}
\Psi(0^2 1^2 0^3 2^1 0^2 1^3 0^1) &=&
y^2 \cdot x \cdot \Psi(0^2 1^2 0^3 2^1 0^2) \cdot \xbar \cdot \Psi(0) \\
&=&
y^2 \cdot x \cdot y \cdot x \cdot \Psi(0^2) 
\cdot \xbar \cdot \Psi(0^3 1^1 0^2) \cdot \xbar \\
&=&
y^2 \cdot x \cdot y \cdot x \cdot y \cdot \xbar 
\cdot x \cdot \Psi(0^3) \cdot \xbar \cdot
\Psi(0^2) \cdot \xbar \\
&=&
y^2 \cdot x \cdot y \cdot x \cdot y \cdot \xbar \cdot x 
\cdot y^2 \cdot \xbar \cdot y \cdot \xbar
\end{eqnarray*}
and
\begin{eqnarray*}
\Psi(0^2 1^1 0^1 2^2 0^2 1^1 0^3 3^1 0^1) &=&
x \cdot \Psi(0^2 1^1 0^1 2^2 0^2) \cdot \xbar \cdot \Psi(0^3 1^1 0^1) \\
&=&
x \cdot x \cdot \Psi(0^2) \cdot \xbar \cdot \Psi(0^1 1^2 0^2)
\cdot \xbar \cdot x \cdot \Psi(0^3) \cdot \xbar \cdot \Psi(0) \\
&=&
x^2 \cdot y \cdot \xbar \cdot y \cdot x 
\cdot \Psi(0) \cdot \xbar \cdot \Psi(0^2) \cdot \xbar \cdot x 
\cdot y^2 \cdot \xbar \\
&=&
x^2 \cdot y \cdot \xbar \cdot y \cdot x  \cdot \xbar \cdot y
\cdot \xbar \cdot x \cdot y^2 \cdot \xbar
\end{eqnarray*}

To conclude this section, we take the example of a 
Hamiltonian circuit (in matrix form)
given at the end of Section 4 and show how 
it translates into a sequence of Motzkin words (as columns).

\begin{center}
  \unitlength=0.7pt
\begin{picture}(220.44,153.10)(4.50,11.45)
 \put(0,0)
 {
	\put(-8.51,-8.44)
	 {
		\put(17.01,16.96){\makebox(0,0)[cc]{1}}
		\put(34.01,16.96){\makebox(0,0)[cc]{1}}
		\put(51.03,16.96){\makebox(0,0)[cc]{1}}
		\put(68.04,16.96){\makebox(0,0)[cc]{1}}
		\put(85.04,16.96){\makebox(0,0)[cc]{1}}
		\put(17.01,33.96){\makebox(0,0)[cc]{0}}
		\put(34.01,33.96){\makebox(0,0)[cc]{0}}
		\put(51.03,33.96){\makebox(0,0)[cc]{1}}
		\put(68.04,33.96){\makebox(0,0)[cc]{0}}
		\put(85.04,33.96){\makebox(0,0)[cc]{0}}
		\put(17.01,50.97){\makebox(0,0)[cc]{1}}
		\put(34.01,50.97){\makebox(0,0)[cc]{1}}
		\put(51.03,50.97){\makebox(0,0)[cc]{1}}
		\put(68.04,50.97){\makebox(0,0)[cc]{1}}
		\put(85.04,50.97){\makebox(0,0)[cc]{1}}
		\put(17.01,67.99){\makebox(0,0)[cc]{0}}
		\put(34.01,67.99){\makebox(0,0)[cc]{0}}
		\put(51.03,67.99){\makebox(0,0)[cc]{1}}
		\put(68.04,67.99){\makebox(0,0)[cc]{0}}
		\put(85.04,67.99){\makebox(0,0)[cc]{1}}
		\put(17.01,84.99){\makebox(0,0)[cc]{1}}
		\put(34.01,84.99){\makebox(0,0)[cc]{1}}
		\put(51.03,84.99){\makebox(0,0)[cc]{1}}
		\put(68.04,84.99){\makebox(0,0)[cc]{0}}
		\put(85.04,84.99){\makebox(0,0)[cc]{1}}
		\put(17.01,102.01){\makebox(0,0)[cc]{1}}
		\put(34.01,102.01){\makebox(0,0)[cc]{0}}
		\put(51.03,102.01){\makebox(0,0)[cc]{0}}
		\put(68.04,102.01){\makebox(0,0)[cc]{0}}
		\put(85.04,102.01){\makebox(0,0)[cc]{1}}
		\put(17.01,119.01){\makebox(0,0)[cc]{1}}
		\put(34.01,119.01){\makebox(0,0)[cc]{0}}
		\put(51.03,119.01){\makebox(0,0)[cc]{1}}
		\put(68.04,119.01){\makebox(0,0)[cc]{1}}
		\put(85.04,119.01){\makebox(0,0)[cc]{1}}
		\put(17.01,136.03){\makebox(0,0)[cc]{1}}
		\put(34.01,136.03){\makebox(0,0)[cc]{0}}
		\put(51.03,136.03){\makebox(0,0)[cc]{0}}
		\put(68.04,136.03){\makebox(0,0)[cc]{0}}
		\put(85.04,136.03){\makebox(0,0)[cc]{1}}
		\put(17.01,153.04){\makebox(0,0)[cc]{1}}
		\put(34.01,153.04){\makebox(0,0)[cc]{1}}
		\put(51.03,153.04){\makebox(0,0)[cc]{1}}
		\put(68.04,153.04){\makebox(0,0)[cc]{0}}
		\put(85.04,153.04){\makebox(0,0)[cc]{1}}
	 }
 }
\put(111,-17.00)
 {
	\put(-8.51,-8.44)
	 {
		\put(17.01,16.96){\makebox(0,0)[cc]{$\bar x$}}
		\put(34.01,16.96){\makebox(0,0)[cc]{$\bar x$}}
		\put(51.03,16.96){\makebox(0,0)[cc]{$\bar x$}}
		\put(68.04,16.96){\makebox(0,0)[cc]{$\bar x$}}
		\put(85.04,16.96){\makebox(0,0)[cc]{$\bar x$}}
		\put(17.01,33.96){\makebox(0,0)[cc]{$x$}}
		\put(34.01,33.96){\makebox(0,0)[cc]{$x$}}
		\put(51.03,33.96){\makebox(0,0)[cc]{$\bar x$}}
		\put(68.04,33.96){\makebox(0,0)[cc]{$\bar x$}}
		\put(85.04,33.96){\makebox(0,0)[cc]{$\bar x$}}
		\put(17.01,50.97){\makebox(0,0)[cc]{$\bar x$}}
		\put(34.01,50.97){\makebox(0,0)[cc]{$\bar x$}}
		\put(51.03,50.97){\makebox(0,0)[cc]{$x$}}
		\put(68.04,50.97){\makebox(0,0)[cc]{$y$}}
		\put(85.04,50.97){\makebox(0,0)[cc]{$x$}}
		\put(17.01,67.99){\makebox(0,0)[cc]{$x$}}
		\put(34.01,67.99){\makebox(0,0)[cc]{$x$}}
		\put(51.03,67.99){\makebox(0,0)[cc]{$\bar x$}}
		\put(68.04,67.99){\makebox(0,0)[cc]{$y$}}
		\put(85.04,67.99){\makebox(0,0)[cc]{$y$}}
		\put(17.01,84.99){\makebox(0,0)[cc]{$\bar x$}}
		\put(34.01,84.99){\makebox(0,0)[cc]{$\bar x$}}
		\put(51.03,84.99){\makebox(0,0)[cc]{$x$}}
		\put(68.04,84.99){\makebox(0,0)[cc]{$x$}}
		\put(85.04,84.99){\makebox(0,0)[cc]{$y$}}
		\put(17.01,102.01){\makebox(0,0)[cc]{$x$}}
		\put(34.01,102.01){\makebox(0,0)[cc]{$y$}}
		\put(51.03,102.01){\makebox(0,0)[cc]{$x$}}
		\put(68.04,102.01){\makebox(0,0)[cc]{$x$}}
		\put(85.04,102.01){\makebox(0,0)[cc]{$y$}}
		\put(17.01,119.01){\makebox(0,0)[cc]{$y$}}
		\put(34.01,119.01){\makebox(0,0)[cc]{$y$}}
		\put(51.03,119.01){\makebox(0,0)[cc]{$y$}}
		\put(68.04,119.01){\makebox(0,0)[cc]{$\bar x$}}
		\put(85.04,119.01){\makebox(0,0)[cc]{$y$}}
		\put(17.01,136.03){\makebox(0,0)[cc]{$y$}}
		\put(34.01,136.03){\makebox(0,0)[cc]{$\bar x$}}
		\put(51.03,136.03){\makebox(0,0)[cc]{$y$}}
		\put(68.04,136.03){\makebox(0,0)[cc]{$y$}}
		\put(85.04,136.03){\makebox(0,0)[cc]{$y$}}
		\put(17.01,153.04){\makebox(0,0)[cc]{$y$}}
		\put(34.01,153.04){\makebox(0,0)[cc]{$x$}}
		\put(51.03,153.04){\makebox(0,0)[cc]{$y$}}
		\put(68.04,153.04){\makebox(0,0)[cc]{$y$}}
		\put(85.04,153.04){\makebox(0,0)[cc]{$y$}}
		\put(17.01,170.05){\makebox(0,0)[cc]{$y$}}
		\put(34.01,170.05){\makebox(0,0)[cc]{$x$}}
		\put(51.03,170.05){\makebox(0,0)[cc]{$y$}}
		\put(68.04,170.05){\makebox(0,0)[cc]{$x$}}
		\put(85.04,170.05){\makebox(0,0)[cc]{$x$}}
		\multiput(8.51,161.54)(17.01,0){5}
 }}
\put(103.60,77.00){\makebox(0,0)[cc]{{\boldmath $\simeq$~~~}}}
\end{picture}




\end{center}
\vskip0.5cm 
\caption{A (matrix) Hamiltonian circuit and its Motzkin translation}\label{012example}


\section{Compatible vectors again}

In this section we point out a simplification 
that is possible in both construcing
the automata ${\cal A}_m$ and computing with them. 
This is due to a simple parity argument
that is inherent in the concept of compatible vectors (or words), 
as introduced in Section 2. 

Consider the following simple transition system on four states, named
00, 01, 10, and 11. 

\begin{center}
\setlength{\unitlength}{0.005000in}%
\begin{picture}(498,369)(124,420)
\thicklines
\put(370,450){\circle*{28}}
\put(532,611){\circle*{28}}
\put(370,770){\circle*{28}}
\put(210,610){\circle*{28}}
\put(370,740){\vector( 0, 1){  0}}
\put(370,740){\vector( 0,-1){260}}
\put(225,595){\vector(-1, 1){  0}}
\put(225,595){\vector( 1,-1){130}}
\put(515,595){\vector( 1, 1){  0}}
\put(515,595){\vector(-1,-1){130}}
\put(355,755){\vector( 1, 1){  0}}
\put(355,755){\vector(-1,-1){130}}
\put(385,755){\vector(-1, 1){  0}}
\put(385,755){\vector( 1,-1){130}}
\put(570,620){\oval(100,20)[r]}
\put(570,610){\vector(-1,0){0}}
\put(170,600){\oval(100,20)[l]}
\put(170,590){\vector(1,0){0}}
\put(400,780){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\rm 00}}}
\put(540,560){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\rm 10}}}
\put(160,640){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\rm 01}}}
\put(400,420){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\rm 11}}}
\end{picture}

\end{center}
\caption{The transition system for compatible vectors}

\vskip0.5cm

To each walk $w$ of length $m$ in this transition graph, given by the
sequence $w = w_0 , w_1 , \ldots , w_n$ of states it visits, 
we associate two words of length $m+1$ over $\{0,1\}$ :
\begin{eqnarray*}
u_w &:=& ~
\hbox{the concatenation of the first components of}~w_0,w_1,\ldots,w_m \\
v_w &:=& ~
\hbox{the concatenation of the second components of}~w_0,w_1,\ldots,w_m
\end{eqnarray*}
It is easy to see that the pairs $(u_w,v_w)$ of words of the same length thus generated
are precisely the pairs of compatible vectors as defined in Section 2.

For ${\cal T}_m$ and ${\cal A}_m$ we need to consider 
(and to produce) all compatible pairs 
$(\overline{u},\overline{v}) = (0 \cdot u \cdot 0,0\cdot v\cdot 0)$ 
with 
$u,v \in \{0,1\}^m$ --- i.e. we have
to consider walks of length $m+1$ starting and 
ending in state 00. Note that each walk
of that kind has an {\em even} number of transitions to or from state 11.
Legal transitions between the other three states, however, have the
property that the generate a factor 00 either in $u_w$ or in $v_w$, but not 
in both words.

This last observation has the following consequence:
call $u \in \{0,1\}^m$ an {\em even} vector if the word 
$\overline{u} = 0 \cdot u \cdot 0$ contains an even number of factors 00, 
otherwise $u$ is {\em odd}. Now, by the previous remark:
\begin{quote}
let $u,v \in \{0,1\}^m$ be vectors such that $\overline{u}$ and $\overline{v}$
are compatible, then
\begin{itemize}
\item[--]
if $m$ is odd, then either both of $u,v$ are even or both are odd
\item[--]
if $m$ is even, then one of $u,v$ is even and the other one is odd
\end{itemize}
\end{quote}

We draw the following consequences:
\begin{itemize}
\item
if $m$ is odd, then $0^m$ is even and only states $q=(u,\pi) \in Q_m$ with
even $u$ are reachable from $0^m$ in ${\cal T}_m$. Hence all the states
$q=(u,\pi)$ with $u$ odd can be eliminated from the construction.
\item
if $m$ is even, then $0^m$ is odd and we need an even 
number of transitions for a walk that 
leads from $0^m$ back to $0^m$, since successive 
states must alternate in ``parity''.
\end{itemize}

The last remark reflects the well known fact that 
$G_{m,n}^*$ has a Hamiltonian circuit
if and only if not both $m$ and $n$ are even.

The next to last remark is illustrated by our example
for $m=3$: there are $\hbox{\em mot}_4 = 9$ states in ${\cal T}_3$, namely
\begin{eqnarray*}
&&(000,\emptyset)~,~(001,1)~,~(010,1)~,~(100,1)~,~
(101,11)~,~(101,12)~,~(111,1)\\
&&(011,1)~,~(110,1)
\end{eqnarray*}    
of which the last two are ``odd'', hence unreachable 
from any of the seven ``even'' states, see Fig.~\ref{auto}.

The precise evaluation of the  size of the set of unreachable states
in the case of odd $m$ will be given elsewhere. 

We conclude this section with a {\em conjecture} 
that has been verified by our computations
up to $m=12$, but for which we are unable to give a proof in general:
\begin{itemize}
\item
in the automaton ${\cal A}_m$, all accessible states
are also coaccessible, i.e. from every state, which is accessible from 
the initial state $\alpha$, 
there is at least one path that leads to the final state $\omega$.
\end{itemize}
If this conjecture were true in general, the minimization procedure 
{\`a la Nerode} for the automaton ${\cal A}_m$ that we employ prior 
to computing the generating function (see the end of the following
section) could be simplified considerably by just identifying states 
that have the same set of successor states.

\section{Computing the generating function $h_m(z)$}
 
From Section 5 we know that the generating function
$h_m(z) = \sum_{n \geq 1} h_{m,n}\,z^n$ is rational.
In this section we informally discuss a way of actually
computing $h_m(z)$, at least for small values of $m$.
As mentioned in the introduction, a program has been written
which carries out these computations for arbitrary $m$ ---
in principle. We have  explicitly computed the
automata ${\cal A}_m$, recognizing the Hamiltonian language
$L_m$, for $m \leq 12$. Some of our results are presented in the  
concluding section. Needless to say that the exponential growth
of ${\cal A}_m$ (in terms of the number of states, as made precise
by the Motzkin-coding in Section 7) puts severe bounds on
practical computations.

A standard way of computing $h_m(z)$ proceeds as follows:
one takes the automaton ${\cal A}_m$ and represents it by 
the transition matrix
\[
{\bf A}_m = \left( a_{p,q}^{(m)} \right)_{p,q \in Q''}
~~\hbox{where}~~
a_{p,q}^{(m)} = \cases{
1 & if $\delta(p,v)=q$ for some $v \in \Sigma_m$ \cr
0 & else}
\]
with $Q_m'' = Q_m' \setminus \{\alpha, \rho\}$. 
Note that, by the definition of ${\cal A}_m$, there is at most one 
$v \in \Sigma_m$ such that $\delta(p,v)=q$, for any $p,q, \in Q_m''$.

Let ${\bf s}$ denote the vector of states immediately acessible from the
initial state $\alpha$ of ${\cal A}_m$ :
\[
{\bf s} = \left( s_p \right)_{p \in Q_m''}
~~\hbox{where}~~
s_p = \cases{
1 & if $\delta(\alpha,u) = p = (u,\pi_{\alpha})$ for some $u \in \Sigma^*$ \cr
0 & else}
\]
and, correspondingly, let ${\bf t}$ denote the vector of terminal states
\[
{\bf t} = \left( t_q \right)_{q \in Q_m''}
~~\hbox{where}~~ 
t_q = \cases{
1 & if $q \in \Omega$ \cr
0 & else}
\]
Then, for any $n \geq 0$,
\[
h_{m,n+1} = {\bf s} \cdot {\bf A}_m^n \cdot {\bf t}^{\tt T}
\]
and thus
\[
h_m(z) = \sum_{n \geq 1} h_{m,n}\,z^n =
z \cdot {\bf s} \cdot ({\bf I}- z \, {\bf A_m})^{-1} \cdot {\bf t}^{\tt T}
\]
where ${\bf I}$ denotes an identity matrix of the same format as ${\bf A}_m$.

Inverting the matrix ${\bf I} - z \, {\bf A}_m$ 
is feasible only for very moderate values of $m$.
One way to compute $h_m(z)$ for larger values of $m$ is by producing
sufficiently many initial coefficients
$h_{m,1} \,,\,h_{m,2}\,,\,h_{m,3}\,,\, \ldots$
using the matrix ${\bf A}_m$ and its powers, and then employing the techniques
of Pad\'e approximation. In particular, the size of the matrix ${\bf A}_m$
gives us an upper bound on the degree of the denominator polynomial
of $h_m(z)$, so that we know in advance when to stop the approximation
procedure. 

A slightly more sophisticated approach that we have experimented 
successfully with for the
purpose of computing $h_m(z)$ is a combination of modular arithmetic
and the Berlekamp-Massey algorithm (see e.g. Section 8.6 in \cite{ln}): 
we compute the residues of the sequence
$h_{m,1} \,,\,h_{m,2}\,,\,h_{m,3}\,,\, \ldots$ modulo various (not too big)
primes $p$ and apply the Berlekamp-Massey algorithm over the finite fields
$GF(p)$ in parallel. 
This gives a very fast way of determining the true degree of the denominator
polynomial of $h_m(z)$. The numerator and denominator polynomial themselves
can then be obtained by Chinese remaindering techniques. A more detailed
description of this approach will be given elsewhere.

One more aspect must be mentioned: the techniques just sketched will not be applied
to the automaton ${\cal A}_m$ and its transition matrix ${\bf A}_m$ themselves.
We will, of course, first apply standard minimization techniques from automata
theory in order to cut down the size of the matrices to be handled, by eliminating
inaccessible states (remember Section 8) and identifying equivalent states.
The minimal automaton $\tilde{\cal A}_m$ obtained from ${\cal A}_m$ gives us a
transition matrix $\tilde{\bf A}_m$ considerably smaller in size, thus leading
to a much better {\em \`a priori} bound on the degree of the numerator polynomial
of the $h_m(z)$. Nonetheless, our numerical results seem to indicate that the
growth rates of the number of states after minimization is of the same order
as the one for the automata ${\cal A}_m$ themselves.
    
\section{Numerical results}

\subsection{The generating functions $h_m(z)/z$ up to $m=8$}\label{gfns}

We give the rational generating functions $h_m(z)/z$ for $1 \leq m \leq 6$ 
and the degrees of the numerator and denominator polynomials for $m = 7,8$.
For these two latter cases the polynomials have been computed explicitly
and are available on request, as are (very large, with $n$ in the thousands)   
initial segments of the coefficient sequences 
$h_{m,n}~(n \geq 1)$ up to $n = 12$.

Note that for $m$ even the generating function $h_m(z)/z$ is actually
``even'' in the sense of being a function of $z^2$. This follows from
the parity argument given in Section 8.

\noindent
    $m = 1$~:
 \[ 
 \frac{1}{-z + 1} =
 1 + z + z^2 + z^3 + z^4 + \ldots
 \]
    $m = 2$~:
 \[ 
 \frac{1}{-2z^{2} + 1} =
 1 + 2z^2+4z^4 + 8 z^6 + 16 z^8 + \ldots
 \]
    $m = 3$~: 
 \[ 
 \frac{1}{-z^{4} + 2z^{3} -2z^{2} -2z + 1} =
 1 + 2z + 6 z^2 + 14 z^3 + 37 z^4 + 92 z^5 + 236 z^6 + \ldots
 \]
    $m = 4$~:
 \[ 
 \frac{3z^{2} + 1}{-2z^{6} - 11z^{2} + 1} =
 1 + 14 z^2 + 154 z^4 + 1696 z^6 + 18684 z^8 + \ldots
 \]
    $m = 5$~: 
% \[ \frac{z^{12} - 2z^{11} + 4z^{10} + 9z^{9} - 15z^{8} + 3z^{7} - 3z^{5}}
%     {-2z^{14} + 4z^{13} - 28z^{12} - 42z^{11}
%     + 82z^{10} + 8z^{9} - 118z^{8} + 66z^{7}} \]
% \[ \dots \frac{+\enspace 24z^{4} - 24z^{3} + 3z^{2} - z + 1}
%     {+\enspace 35z^{6} - 90z{5} - 12z^{4} + 63z^{3} - 14z^{2} - 5z + 1 } \]
 \[ \frac{ \left(z-1\right) (z^{11}-z^{10}+3\,z^{9}+12\,z^{8}-3\,z^{7}}
     {-2z^{14} + 4z^{13} - 28z^{12} - 42z^{11}
     + 82z^{10} + 8z^{9} - 118z^{8} + 66z^{7}} \]
 \[ \cdots \frac{-\enspace 3\,z^{4}+21\,z^{3}-3\,z^{2}-1)}
     {+\enspace 35z^{6} - 90z{5} - 12z^{4} + 63z^{3} - 14z^{2} - 5z + 1 } \]
 \[ =
 1 + 4 z + 37 z^2 + 154 z^3 + 1072 z^4 + 5320 z^5 + 32675 z^6 + 
 175294 z^7 + 1024028 z^8 + \ldots
 \]
    $m = 6$:
 \[ \frac{96z^{32} - 48z^{30} - 4592z^{28} - 9162z^{26} + 64012z^{24}
     - 252197z^{22} }
     {-144z^{36} \!-\! 1728z^{34} \!+\! 5972z^{32}\!-\! 17732z^{30} \!-\! 92790z^{28}
     \!+\! 178842z^{26} \!+ \! 1036420z^{24} } \]
 \[ \cdots \frac{+\enspace 643288z^{20} - 797154z^{18} + 453054z^{16}
     - 40229z^{14} }
     {-\enspace 3390877z^{22} + 4008954z^{20} - 2681994z^{18} + 1690670z^{16}
     - 1251439z^{14} } \]
 \[ \cdots \frac{-\enspace 111603z^{12} + 87046z^{10} - 33250z^{8}
     + 6525z^{6} - 568z^{4} + 7z^{2} + 1}
     {+\enspace 815141z^{12} - 386724z^{10} + 116734z^{8}
     - 20403z^{6} + 1932z^{4} - 85z^{2} + 1 } \]
 \[ =
 1 + 92 z^2 + 5320 z^4 + 301384 z^6 + 17066492 z^8 + 966656134 z^{10}
  + \ldots
 \]
 \bigskip

 \noindent
    $m = 7$~: degree of numerator~: 64, degree of denominator~: 66.
  \[
  1 + 8z + 236 z^2 + 1696 z^3 + 32675 z^4 + 301384 z^5 +
  4638576 z^6 + 49483138 z^7 + \ldots
  \]
 \bigskip

 \noindent
    $m = 8$~: degree of numerator~: 206, degree of denominator~: 208.
  \[
  1 + 596 z^2 + 175294 z^4 + 49483138 z^6 + 13916993782 z^8 +
  3913787773536 z^{10} + \ldots
  \]

The reader may check the obvious property $h_{m,n} = h_{n,m}$
from these data.
 
\subsection{Data of the computed automata (matrices)}\label{counts}

 \begin{minipage}{7.5cm}
 \begin{tabular}{|r|r|r||r|r|}
  \hline
   & \multicolumn{2}{c||}{ num.~of states }
   & \multicolumn{2}{c|} { num.~of transitions } \\
  \hline
   m & {\Huge \phantom{a} } ${\cal A}_m$ & $\tilde {\cal A}_m$ & ${\cal A}_m$
     & $\tilde {\cal A}_m$ \\
  \hline
   1  & 3	& 3	& 3	  & 3 		\\
   2  & 5	& 4	& 6	  & 5		\\
   3  & 10	& 6	& 20	  & 14		\\
   4  & 22	& 13	& 64	  & 44		\\
   5  & 52	& 22	& 224	  & 121		\\
   6  & 128	& 74	& 803	  & 543		\\
   7  & 324	& 117	& 2966	  & 1396	\\
   8  & 836	& 461	& 11133	  & 7349	\\
   9  & 2189	& 728	& 42409	  & 18285	\\
   10 & 5799	& 3094	& 163295  & 105154	\\
   11 & 15512	& 4828	& 634700  & 255196	\\
   12 & 41836	& 21552	& 2486247 & 1556317 	\\
%   1  & 1	& 1	& 1	  & 1 		\\
%   2  & 3	& 2	& 4	  & 3		\\
%   3  & 8	& 4	& 16	  & 10		\\
%   4  & 20	& 11	& 58	  & 38		\\
%   5  & 50	& 20	& 214	  & 111		\\
%   6  & 126	& 72	& 787	  & 527		\\
%   7  & 322	& 115	& 2940	  & 1370	\\
%   8  & 834	& 459	& 11091	  & 7307	\\
%   9  & 2187	& 726	& 42341	  & 18217	\\
%   10 & 5797	& 3092	& 163185  & 105044	\\
%   11 & 15510	& 4826	& 634522  & 255018	\\
%   12 & 41834	& 21550	& 2485959 & 1556029 	\\
  \hline
 \end{tabular}
 \end{minipage}
 \begin{minipage}{5.0cm}
 \begin{itemize}
  \item[ ] The number $\sharp Q_m'$ of states of ${\cal A}_m$ 
  equals $\hbox{\em mot}_m+1$. The size $\sharp Q_m''$  of ${\bf A}_m$ 
  equals $\hbox{\em mot}_m-1$. Similarly, $\tilde {\cal A}_m$ 
  is bigger by 2 than $\tilde {\bf A}$.
% \item The number of transitions of ${\cal A}_m$ and $\tilde {\cal A}_m$
%   equals the sum of the elements of the corresponding 
%   matrix. This is
%   (in the case of $A_m$ only) the number of positive entries, i.e. 1's.
 \end{itemize}
 \end{minipage}

\subsection{Computation times and memory use}\label{messungen}
 \begin{minipage}{4.5cm}
 \begin{tabular}{|c|r|r|}
  \hline
  m & cpusec & bytes\\
  \hline
  1 &	  .0394 &	24 \\
  2 &	  .0448 &	46 \\
  3 &	  .0656 &	150 \\
  4 &	  .0946 &	254 \\
  5 &     .9802 &	2166 \\
  6 &   20.4996 &	21920 \\
  7 & 2189.6090 &	350512 \\
  8 & 2251385.5 &	26895646 \\ 
  \hline
 \end{tabular}
 \end{minipage}
 \hfill
 \begin{minipage}{7.7cm}
 These are the average computation times for the generating functions.
 The bytes column shows the maximum memory need of the main datastructures
 of the program. The computations reported here have been done on a {\sc sparc 2}
 (30MHz). The computation for $m=8$ was performed on a {\sc sparc 10}.
 \end{minipage}
\newpage
 
\begin{thebibliography}{99}
  \bibitem{br} Berstel, Jean and Reutenauer, Christophe~:
  {\em Rational series and their languages}.
  Springer, Berlin 1988.
 \bibitem{hu} Hopcroft, John E.~and Ullman, Jeffrey D.~:
  {\em Introduction to Automata Theory, Languages and Computation}.
  Addison-Wesley 1979.
 \bibitem{kreweras} Kreweras, Germain~: 
  D\'enombrement des Cycles Hamiltoniens dans un Rectangle Quadrill\'e.
  {\em European Journal of Combinatorics} {\bf 13} (1992), 473-467.
 \bibitem{kwong} Kwong, Harris~: 
  Enumeration of Hamiltonian Cycles in
  $P_{4}\times P_{n}$ and $P_{5}\times P_{n}$.
  {\em Ars Combinatoria} {\bf 33} (1992), 87-96.
  \bibitem{rogers} Kwong, Harris and Rogers, D.~G.~: 
  A Matrix Method for Counting Hamiltonian Cycles on Grid Graphs. 
  To appear in {\em European Journal of Combinatorics}.
 \bibitem{ln} Lidl, Rudolf and Niederreiter, Harald~:
  {\em Finite Fields} (Encyclopedia of Mathematics
  and its Applications, vol. 20), 
  Cambridge University Press, 1984.
 \bibitem{stanley} Stanley, Richard P.~: 
  {\em Enumerative Combinatorics}.
  Wadsworth \& Brooks/Cole, Monterey, California 1986.
 \bibitem{stoyan} Stoyan, Robert~: 
  {\em Anzahl der Hamilton-Kreise in rechteckigen Gittern}. 
  Studienarbeit im Fach Informatik an der Universit\"at
  Erlangen-N\"urnberg, 1993.
\end{thebibliography}      



\end{document}
