\input amstex
\input amsppt.sty

\nologo

\magnification1200
\hsize13cm
\vsize19cm

\def\al{\alpha}
\def\be{\beta}
\def\Om{\Omega}
\def\Si{\Sigma}
\def\om{\omega}
\def\F{\Cal F}

\topmatter 
\title Some combinatorial properties of complete semi-Thue systems
\endtitle 
\author Winfried Kurth
\endauthor 
\address 
Technische Universit\"at Clausthal, Institut f\"ur Mathematik,
Erzstr.~1, D-3392\break Claus\-thal--Zellerfeld  
\endaddress

\endtopmatter
\document

A {\it reduction system} $(R,\longrightarrow)$ consists of a set $R$
and a binary relation $\longrightarrow$ on $R$. Let $\overset
*\to\longrightarrow$ be the reflexive-transitive closure of
$\longrightarrow$ and $[x]$ the class of an $x\in R$ with respect to
the equivalence generated by $\longrightarrow$. $x$ is called {\it
irreducible} (or {\it in normal form}) if there is no $y\in R$ such
that $x\longrightarrow y$. A reduction system can have the following
properties: 

\roster 
\item "$\bullet$" {\it Chain Condition:} There is no infinite chain
$x_1 \longrightarrow x_2\longrightarrow x_3\longrightarrow 
\cdots$ in $R$. (Then $\longrightarrow $ is called {\it terminating}
or {\it Noetherian}.)
\item "$\bullet$" {\it Confluence:} $\forall w$, $x$, $y\in R$:
($w\overset*\to\longrightarrow x\ \land\ w\overset *\to\longrightarrow
y\Rightarrow \exists z\in R:\ x\overset*\to\longrightarrow  z\ \land\
y\overset *\to\longrightarrow z$).
\item "$\bullet$" {\it Completeness:} Chain condition and confluence.
\endroster

If a reduction system is complete, normal forms always exist and are
unique. See \cite{3} for further details. 

Let $\Sigma$ be a finite alphabet. $\Sigma^*$ denotes the free monoid
over $\Sigma$ and $\square$ the empty word. A {\it semi-Thue system}
(STS) on $\Si$ is a subset $S\subseteq\Si^*\times \Si^*$. Each element
$(u,v)$ of $S$ is called a {\it rule} and written in the form
$u\longrightarrow v$. An STS $S$ defines a reduction relation
$\longrightarrow $ on $\Si^*$ by $xuy\longrightarrow xvy$
$\Leftrightarrow$ $(u,v)\in S$.

Let $OV(u)=\{x\in \Si^*\mid \exists y, z\in\Si^*: \
u=yx=xz\}\backslash \{\square,u\}$ be the set of {\it non-trivial
self-overlaps} of $u\in \Si^*$. Generalizing results of Book \cite{2},
Otto and Wrathall \cite{6}, one obtains the following.

\proclaim{Theorem} Let the single-rule STS $u\longrightarrow v$
satisfy the chain condition, and let $u=u_0u_1u_2\dots u_k$ ($k\ge0$),
such that $OV(u)=\{u_1u_2\dots u_k,u_2\dots u_k,\dots,u_k \}$. The STS
is confluent if and only if one of the following two conditions is satisfied:

\roster 
\item "(a)" $v$ has $u_1u_2\dots u_k$ as a self-overlap, or
\item "(b)" there is a $j\in \{1,2,\dots,k+1\}$, such that
$v=u_ju_{j+1}\dots u_k$ {\rm(}for $j=k+1${\rm:} $v=\square${\rm)} and
$u=u_{j-1}^ju_ju_{j+1}\dots u_k$. 
\endroster
\endproclaim

For the case $v=\square$, this means that $u$ must be a power of a
word $y$ without proper self-overlap \cite{2}. The classes $\vert
w\vert$ of such complete systems $y^r\longrightarrow \square$ are
deterministic context-free languages \cite{1}. One can show that the
unambiguous grammar $(\Si\cup\{S\},\,\Si,\,P,\,S)$ with
$P=\{S\longrightarrow \square,\ S\longrightarrow (a_1Sa_2S\dots
a_{k-1}Sa_k)^rS \}$, where $y=a_1a_2\dots a_k$ ($a_i\in \Si$),
generates $\vert\square\vert$. (There is a similar grammar for the
general case $\vert w\vert$.) From this presentation it follows that
the structure generating function $S(z)$ (cf\. \cite{4}) of
$\vert\square\vert$ is the unique solution of the equation
$S(z)=1+z^{rk}(S(z))^{r(k-1)+1}$ in $\Bbb Z[[z]]$, which is a variant
of the well-known ``trinomial equation" (T): $A(x)=1+x(A(x))^t$ ($t\in
\Bbb N$). (T) has the unique solution $A(x)=\sum _{n=0}
^{\infty}a_nx^n$ with $a_n=\frac {1} {n(t-1)+1}\binom {tn}n$ (the
$a_n$ having a lot of combinatorial interpretations, see, e.g.,
\cite{5}). This is usually proved by the Lagrange inversion formula,
but it can also be deduced from the set equation
$[a^p]=[a^{p-1}]a+[a^{p+k-1}]b $ for the special STS
$a^{k-1}b\longrightarrow \square$. The enumeration of words in the
classes $[w]$, $w$ irreducible, can be carried out in the same manner.




\Refs
\ref\key 1\by R. V. Book\paper Confluent and other types of Thue
systems\jour J. ACM\vol 28\yr 1982\pages 171--182\endref

\ref\key 2\by \bysame\paper A note on special Thue systems with a
single defining relation\jour Math\. Systems Th\.\vol 16\yr 1983\pages
57--60\endref

\ref\key 3\by G. Huet\paper Confluent reductions: abstract properties
and applications to term rewriting systems\jour J. ACM\vol 27\yr
1980\pages 797--821 \endref

\ref\key 4\by W. Kuich\paper On the entropy of context-free
languages\jour Information and Control\vol 16\yr 1970\pages 173--200\endref

\ref\key 5\by \bysame\paper A context-free language and enumeration
problems of infinite trees and digraphs\jour J. Combin\. Theory
Ser.~B\vol 10\yr 1971\pages 135--142\endref

\ref\key 6\by F. Otto and C. Wrathall\paper A note on Thue systems
with a single defining relation\jour Math\. Systems Th\.\vol 18\yr
1985\pages 135--143\endref


\endRefs





\enddocument
