\documentstyle[12pt]{article} \setlength{\oddsidemargin}{10pt} \setlength{\evensidemargin}{10pt} \setlength{\marginparwidth}{0pt} \setlength{\marginparsep}{0pt} \setlength{\topmargin}{-40pt} \setlength{\textwidth}{450pt} \setlength{\textheight}{630pt} \setlength{\tabbingsep}{0pt} \setlength{\headsep}{30pt} \setlength{\fboxsep}{40pt} \setlength{\fboxrule}{4pt} \setlength{\footnotesep}{20pt} \raggedright \setlength{\parindent}{25pt} \setlength{\parskip}{8pt plus 5pt} \begin{document} \title{THE FINITENESS OF FINITELY PRESENTED MONOIDS\footnote{ This paper is dedicated to the memory of Marco Sch\"{u}tzenberger, the one most responsible for impressing upon me the importance of monoids.}} \author{Robert McNaughton\thanks{Supported by Grant No. CCR-9500182 from the National Science Foundation. I am grateful for the crucial guidance of Friedrich Otto in this research, and also for his critical reading of this paper.} \\ Department of Computer Science \\ Rensselaer Polytechnic Institute \\ Troy, NY 12180-3590, U.S.A. \\ mcnaught@cs.rpi.edu} \date{April, 1997} \maketitle {\bf Introduction.} It is undecidable whether a monoid given by a finite presentation is finite (see, e.g., \cite{bo}, pp. 157--160). On the other hand, with the mere knowledge that the monoid is finite, one can effectively construct the multiplication table of the monoid, and thus obtain a complete understanding of its structure. This paper will present this construction method in detail (Section~2) and offer some remarks about its computational complexity (Section~3). The notation here will be based on \cite{bo}, whose final chapter furnishes much of the background and will be referenced frequently. It is convenient to think of a finite monoid presentation as a Thue system, i.e., an ordered pair $(\Sigma , R)$, where $\Sigma$ is a finite alphabet (or set of generators) and $R$ is a finite set of unordered pairs of strings over $\Sigma$, called the ``set of rules.'' For $(y_1 ,y_2 ) \in R$ and $x,z \in \Sigma ^*$ one writes $xy_1 z \leftrightarrow xy_2 z$ and $xy_2 z \leftrightarrow xy_1 z$; thus the rules operate symmetrically. One writes $x \leftrightarrow ^* y$ to assert the existence of a {\em derivation\/} of $y$ from $x$, i.e., a~sequence \[ x_0 = x,x_1 , \ldots , x_p = y~(p \geq 0), \mbox{ where } x_i \leftrightarrow x_{i+1} \mbox{ for each } i \leq p-1 \] When $x \leftrightarrow ^* y$ holds one says that $x$ and $y$ are {\em congruent.\/} For brevity, the $\leftrightarrow ^*$ relation is written as $\equiv$. It is clearly a congruence relation, since it is reflexive, symmetric and transitive, and since, for all $x,y_1 ,y_2,z \in \Sigma ^*$, $y_1 \equiv y_2$ implies $xy_1 z \equiv xy_2 z$. For the presentation $P= (\Sigma ,R)$, $M(P)$ is defined to be the monoid whose elements are the congruence classes of $\Sigma ^*$ of the Thue system congruence $\equiv$. For $w \in \Sigma ^*$, $[w]$ is defined to be the congruence class $\{ x|x \equiv w \}$. Thereupon the set of elements of $M(P)$ is $\{ [w]~|~w \in \Sigma ^* \}$. Monoid multiplication is defined as $[x][y] = [xy]$. Where $e$ is the null word, i.e., the word of length $0$, $[e]$ is the monoid identity (since $[e][x] = [x][e] = [x]$, for all $x$). Since word concatenation is associative, multiplication in $M(P)$ is associative; so $M(P)$ is indeed a monoid. For $x \in \Sigma ^*$, $|x|$ is the length of $x$. For $M$ a monoid, $|M|$ is the order of~$M$. {\bf Theorem 1.1.} If $x \in \Sigma ^*$ and $x$ is not congruent modulo $P$ to any shorter word then $|M(P)| \geq |x| + 1$. {\em Proof:\/} If $x = x'x''x'''$ with $|x''| > 0$ and $x' \equiv x'x''$ then $x \equiv x'x'''$ where $|x'x'''| < |x|$. From this it follows that if $x$ is not congruent to any shorter word then no two prefixes of $x$ are congruent. Since $x$ has $|x| + 1$ prefixes, including $e$ and $x$ itself, there are at least $|x| + 1$ congruence classes, viz., $|M(P)| \geq |x| + 1.\Box$ We offer two examples with $\Sigma = \{ b,c \}$. For $P_1 = ( \Sigma , \{ (bc,e) \} )$, $M(P_1)$ turns out to be an infinite monoid, known as the ``bicyclic monoid'' or ``bicyclic semigroup,'' whose elements are of the form $[c^ib^j]$, $i,j \geq 0$, where $[e = c^0b^0]$ is the monoid identity and the product is \[ [c^ib^j][c^kb^m] = \left\{ \begin{array}{ll} [c^{i+k-j}b^m] & \mbox{if $j \leq k$} \\ [c^ib^{m+j-k}] & \mbox{if $j > k$} \end{array} \right. \] (There are some who might want to regard this expression as a multiplication table. However, this paper will consider multiplication tables only for finite monoids.) On the other hand, for the example \[ P_2 = ( \Sigma , \{ (bbb,bb),(cc,c),(bc,c),(cbb,bb) \} ) \] $M(P_2)$ is finite. The five monoid elements are the five congruence classes $[e] = \{ e \} $, $[b] = \{ b \}$, $[bb] = \{ \Sigma ^*bb \}$, $[c] = \{ \Sigma ^*c \}$ and $[cb] = \{ \Sigma ^*cb \}$. The multiplication table is depicted here with one column for each monoid element but with rows corresponding only to the monoid generators. In the following table for $M(P_2)$, each entry is the result of the product of the column element (left factor) by the row element (right factor): \begin{center} $ \begin{array}{cccccc} & [e] & [b] & [bb] & [c] & [cb] \\ b & [b] & [bb] & [bb] & [cb] & [bb] \\ c & [c] & [c] & [c] & [c] & [c] \end{array} $ \end{center} The entire multiplication table could easily be written from this abbreviated table;~e.g., \[ [cb][cb] = ([cb]c)b = [c]b = [cb] \] The problem of the finiteness of finitely presented monoids is somewhat similar to the problem of whether a given Thue system has an equivalent (finite) confluent system, with respect to a given ordering of strings. Indeed the Knuth-Bendix completion procedure (\cite{kb}, see also \cite{kn}) is a semi-algorithm for this problem: it terminates with an equivalent confluent system if there is one, but fails to terminate if there is none. Furthermore, the Knuth-Bendix procedure could be used as a semi-algorithm for the finiteness problem of finitely presented monoids, as will be explained at the end of Section~2. The Todd-Coxeter procedure \cite{tc}, which has as its goal the enumeration of the cosets of a subgroup in a group, can be used to construct the multiplication table of a finite group from a given finite presentation. It is quite similar to the algorithm that will be given in the next section, which could be thought of as its generalization to monoids. The Todd-Coxeter procedure begins with a subgroup $H$ of a given finitely presented group $G$, enumerates the cosets of $H$ in $G$, and produces a multiplication table containing all products of the form $H_ib = H_j$, where $H_i$ and $H_j$ are cosets of $H$ and $b$ is a generator of $G$. One way of using the Todd-Coxeter procedure to find the multiplication table of a group $G$ is simply to take $H$ as the trivial subgroup of $G$, whereupon the cosets of $H$ are the singleton sets, identifiable with the elements of $G$. Coset enumeration in general, including the Todd-Coxeter procedure in particular, plays a prominent r\^{o}le in computational group theory (see, e.g., \cite{si}, especially, pp. 175--196). A proof that the procedure does terminate and produce all the cosets, in cases where the subgroup $H$ is of finite index in $G$, can be found in \cite{me}. In the remainder of this paper the word ``presentation'' will always mean a finite monoid presentation. \vspace{.5in} {\bf 2. The construction.} This section puts forth a procedure that, from a given presentation, terminates if and only if the monoid is finite; upon termination it yields the multiplication table of the monoid. Let $T = (\Sigma ,R)$ be the presentation, i.e., a Thue system as explained in Section~1. We require a refinement of the congruence relation $\equiv$: {\bf Definition:} $x \equiv _n y$ means that $|x| \leq n$, $|y| \leq n$ and there is derivation of $y$ from $x$ in $(\Sigma ,R)$ in which no word has length greater than $n$. Note that (1)~the 3-place predicate $x \equiv _n y$ is decidable. For each $n$, (2)~the relation $\equiv _n$ may be thought of as a congruence relation over $(\Sigma \cup \lambda )^n$ but (3)~it is certainly not a congruence relation over~$\Sigma ^*$. {\bf Definition:} $D(k,n)$ is the following predicate over the positive integers: for every word $w$ of length $k$, there is a word $w'$ of smaller length such that $w \equiv _n w'$. Note that $D(k,n)$ implies $k \leq n$, and that $D$ is a decidable predicate. The reader is also asked to verify that it is decidable whether, for any given $n$, there exists $k$ such that $D(k,n)$. {\bf Theorem 2.1.} $M(P)$ is finite if and only if there exist $k$ and $n$ such that $D(k,n)$ holds. {\em Proof:\/} Assume $D(k,n)$. Since every word of length $k$ is congruent to a word of smaller length, every word of length $\geq k$ is congruent to a shorter word. From this it follows that every word of length $\geq k$ is congruent to a word of length less than $k$. Thus $M(P)$ is finite. For the converse, assume $M(P)$ is finite. For each $x \in \Sigma ^*$, let $h(x) =$ the length of the shortest word congruent to $x$. The set $H = \{ h(x) ~|~x \in \Sigma ^* \}$ is bounded, since $M(P)$ is finite. Take $k = 1~+$ the maximum element of $H$. For each $y \in \Sigma ^k$, there is a derivation from $y$ to a shorter word. Since there are finitely many such $y$ there are finitely many such derivations, each of which is a finite sequence of words. Thus the set of all words occurring in all the derivations has a maximum length $n$. For these values of $k$ and $n$, $D(k,n)$ holds.$\Box$ {\bf Definition:} $n_0 =$ the smallest value of $n$ such that $D(k,n)$ is true for some $k$; it is undefined if $M(P)$ is infinite. In order to search for $n_0$, we construct tables for the relations $\equiv _1 ,~ \equiv _2 ,~ \cdots ~$ such that the entries for $\equiv _n$ are all words of length $\leq n$. The table for $\equiv _{n+1}$ is readily constructed from the table for $\equiv _n$. Indeed, if we take \[ Q_{n+1} = \{ |~|x| = n+1, |y| \leq n+1, x \leftrightarrow y \} \] then $\equiv _{n+1}$ is the symmetric and transitive closure of the relation \[ Q_{n+1}~ \cup ~ \equiv _n ~ \cup ~ \{ |~|x| = n+1 \} \] For the remainder of this section, we assume that $n_0$ has been found and therefore $M(P)$ is finite. Since every word of length $n_0$ is congruent to a word of smaller length, every word of length $\geq n_0$ is congruent to a word of length less than $n_0$. An often-used total ordering of all words of $\Sigma ^*$ is the {\em length-lexicographic ordering\/}. We shall use the symbol $<$ for this ordering, writing $w_1 < w_2$ ($w_1,w_2 \in \Sigma ^*$) if either $|w_1| < |w_2|$ or else $|w_1| = |w_2|$ and $w_1$ precedes $w_2$ lexicographically. For example, if $b,c,d \in \Sigma$ with $b < c$ and $c < d$, then $bcc < bdb$ and $dd < bbb$. {\bf Definition:} For $|x| \leq n_0$, let $f(x) =$ the smallest word $w$ in the sense of the length-lexicographic ordering relation such that $w \equiv _{n_0} x$. Note that, for all such $x$, $|f(x)| \leq n_0 - 1$. Let the range of $f$ (which is finite) be $\{ w_1 = e,w_2, \ldots ,w_p \}$. Form the directed graph $G_1$ as follows: The nodes are labeled $w_1 ,w_2 , \ldots ,w_p$; $w_1 = e$ is called the ``initial node.'' For all $w_i,w_j$ and $b$, there is an arc labeled $b$ from $w_i$ to $w_j$ if $f(w_i b) = w_j$; there are no arcs other than these. {\bf Definition:} We write $\delta (w_i ,x) = w_j$ if there is a walk in $G_1$ from node $w_i$ to node $w_j$ whose labels in order spell out the word $x$. For $x = e$, $w_j = w_i$ and the walk is the null walk on $w_i$. {\bf Theorem 2.2.} For all $x \in \Sigma ^*$, there is a walk in $G_1$ spelling out $x$ from $e$ to~$\delta (e,x)$. {\em Proof:\/} First note that, for $b \in \Sigma$, if node $N$ has label $w$ then $|w| < n_0$, $|wb| \leq n_0$ and $|f(wb)| < n_0$. So there is an arc labeled $b$ from node $w~(=N)$ to node $f(wb)$. From this our theorem follows by induction on the length of $x$ (the basis being the null walk on $e).\Box$ {\bf Theorem 2.3.} For all $x \in \Sigma ^*$, $\delta (e,x) \equiv x$. {\em Proof by induction on $|x|$:\/} Clearly our theorem is true for $x = e$. Assume $w_i = \delta (e,x) \equiv x$. For $b \in \Sigma$, we have $\delta (e,xb) = \delta (w_i,b) = w_j$, where $w_j = f(w_i b)$. By definition of $f$, $w_j \equiv _{n_0} w_i b$, which implies $w_j \equiv w_i b$. Thus \[ \delta (e,xb) = w_j \equiv w_ib \equiv xb \mbox{ (since } w_i \equiv x).\Box \] {\bf Corollary.} For all $x,y \in \Sigma ^*$, if $\delta (e,x) = \delta (e,y)$ then $x \equiv y$. For $|x|,|y| \leq n_0$, $x \equiv _{n_0} y$ implies $x \equiv y$. However, the converse may not hold, as shown in Example~1 at the end of this section. Consequently, the graph $G_1$ may not have the converse to the property of the last Corollary, which we need. In general, therefore, the graph $G_1$ needs to be simplified to a graph that has both properties. Accordingly, a sequence of graphs, $G_2 , \cdots ,G_p$ will be constructed so that $G_p$ will have the following properties: \begin{quote} (1) if $\delta (e,x) = \delta (e,y)$ in $G_p$ then $x \equiv y$; (2) if $x \equiv y$ then $\delta (e,x) = \delta (e,y)$ in $G_p$; and (3) $G_p$ is deterministic. \end{quote} The graph $G_1$ has properties~(1) and~(3). It does not have property~(2) unless $p = 1$. As we shall see, $G_2 , \ldots G_{p-1}$, which may or may not have property~(3), all have property~(1) but not property~(2). For $1 \leq i \leq p-1$, $G_{i+1}$ is obtained from $G_i$ by merging two nodes, as will now be prescribed: {\bf Definition:} For any node $N$ in a graph $G$, $L_G(N) = \{ x|x$ is spelled out by a walk from the initial node to $N$ in $G \}$. Note that if there is an arc labeled $b$ from node $N$ to node $N'$ in $G$ then $L_G(N)b \subseteq L_G(N')$. ($L_G(N)b$ means $\{ wb | w \in L_G(N) \}$.) {\bf Definition:} The nodes $N_1$ and $N_2$ of a graph are an {\em eligible pair for merging\/} if $N_1 \neq N_2$ and either (1)~there are a node~$N_4$, a letter~$b$, an arc from $N_4$ to $N_1$ labeled $b$ and an arc from $N_4$ to $N_2$ labeled $b$, or else (2)~there are a node $N_4$, a rule $(u,v)$, a walk from $N_4$ to $N_1$ spelling out $u$ and a walk from $N_4$ to $N_2$ spelling out $v$. ($N_4$ may be the same as $N_1$ or $N_2$, or may differ from each.) For each $i$, $G_{i+1}$ is obtained from $G_i$ by merging some eligible pair of nodes. When node $N_1$ and $N_2$ in $G_i$ are merged, they are replaced by a single node $N_3$ in $G_{i+1}$; all arcs entering either $N_1$ or $N_2$ now enter $N_3$, and all arcs leaving $N_1$ or $N_2$ now leave $N_3$. Other nodes and arcs in $G_{i+1}$ are the same as in $G_i$. The initial node of $G_i$, merged or unmerged, becomes the initial node of $G_{i+1}$. {\bf Theorem 2.4.} For every $G_i$ and $x \in \Sigma ^*$, there is at least one node $N$ such that $x \in L_{G_i}(N)$. {\em Proof by induction on $i$:\/} The truth for $G_1$ follows from Theorem~2.2. By construction, if it holds for $G_i$ it holds for $G_{i+1}.\Box$ {\bf Theorem 2.5.} (1)~For any node $N$ of any $G_i$, the words in the set $L_{G_i}(N)$ are all congruent to one another. And (2)~for any two nodes $N_1$ and $N_2$ eligible for merging, the words in the set $L_{G_i}(N_1) \cup L_{G_i}(N_2)$ are all congruent to one another. {\em Proof:\/} By the Corollary to Theorem~2.3, (1)~is true of $G_1$. The proof of our theorem will be by mathematical induction on $i$ and the strategy will be to prove first Part~a: if (1)~holds for $i$ then (2)~holds for $i$; and then Part~b: if (1)~and (2)~hold for $i < p$ then (1)~holds for $i+1$. {\em Part a:\/} Assume (1) is true for $G_i$ and let $N_1, N_2 \in G_i$ be eligible for merging. Case I: for some $b \in \Sigma$, there are arcs labeled $b$ from some node $N_4$ to $N_1$ and from $N_4$ to $N_2$. Let $y \in L_{G_i}(N_4)$. Then $yb \in L_{G_i}(N_1)$ and $yb \in L_{G_i}(N_2)$. From this fact and~(1) for $G_i$, it follows that all words of $L_{G_i}(N_1) \cup L_{G_i}(N_2)$ are congruent to one another. Case II: for some node $N_4$ of $G_i$, there is a walk from $N_4$ to $N_1$ spelling out $u$ and a walk from $N_4$ to $N_2$ spelling out $v$, where $(u,v)$ is a rule. Then $yu \in L_{G_i}(N_1)$ and $yv \in L_{G_i}(N_2)$. Since $yu \equiv yv$ and (1)~is true for $G_i$, all words of $L_{G_i}(N_1) \cup L_{G_i}(N_2)$ are congruent to one another. {\em Part b:\/} Assume (1) and (2) are true of $G_i$. For every node $N \in G_i$, let $con_i(N)$ be the common congruence class of the words spelled out by walks in $G_i$ from the initial node to $N$. We define a function $con'_{i+1}$ over the nodes of $G_{i+1}$: \[ con'_{i+1}(N) = \left\{ \begin{array}{ll} ~~~~~~~con_i(N) & \mbox{ if $N \neq N_3$} \\ con_i(N_1) = con_i(N_2) & \mbox{ if $N = N_3$} \end{array} \right. \] {\bf Lemma b1.} If there is an arc labeled $b$ from $N$ to $N'$ in $G_{i+1}$ then $con'_{i+1}(N') = [wb]$, where $w$ is any word in $con'_{i+1}(N)$. {\em Proof:\/} Case I: $N \neq N_3 \neq N'$. Then $N,N'$ and the arc joining them are in $G_i$; and $con'_{i+1}(N) = con_i(N)$ and $con'_{i+1}(N') = con_i(N') = [wb]$ for any $w \in con_i(N)$. Case II: $N = N_3 \neq N'$. Then there is an arc in $G_i$ labeled $b$ either from $N_1$ to $N'$ or from $N_2$ to $N'$; without loss of generality assume the former. The set $con'_{i+1}(N') = con_i(N') = [wb]$ for any $w \in con_i(N_1) = con'_{i+1}(N_3)$. The proofs of the remaining two cases are left to the reader: Case III: $N \neq N_3 = N'$. Case IV: $N = N_3 = N'$. (Note that, in this case, there is an arc in $G_i$ labeled $b$ either from $N_1$ to $N_1$, from $N_1$ to $N_2$, from $N_2$ to $N_1$ or from $N_2$ to $N_2.)\Box$ {\bf Lemma b2.} For all nodes $N$ of $G_{i+1}$, $L_{G_{i+1}}(N) \subseteq con'_{i+1}(N)$. The proof consists of proving by use of Lemma~b1 that, for any walk $W$ in $G_{i+1}$ from the initial node to $N$, if $W$ spells out $w \in \Sigma ^*$ then $w \in con'_{i+1}(N)$. This proof, which is by induction on the length of the walk $W$, is left to the reader. Lemma~b2 completes part~(b) and, with it, the entire proof of Theorem~2.5.$\Box$ {\bf Theorem 2.6.} (1)~The sequence $G_1 ,G_2 , \ldots ~$ is finite. That is to say, there exists a $p$ such that no two nodes of $G_p$ are eligible for merging. (2)~$G_p$ is deterministic. {\em Proof:\/} For (1), note that the number of graph nodes in each graph in the sequence decreases by 1 each time. For (2) assume $G_i$ is nondeterministic. Then for some node $N_3$ of $G_i$ and some letter $b$, $\delta (N_3,b)$ has at least two values in $G_i$, say $N_1$ and $N_2$, eligible for merging. Hence, $i \neq p.\Box$ {\bf Theorem 2.7.} If in $G_i$, $N_1 \neq N_0$, $x \in L_{G_i}(N_1)$, $y \in L_{G_i}(N_0)$ and $x \equiv y$, then $G_i$ has a pair of nodes eligible for merging. {\em Proof:\/} If for some node $N_4$ of $G_i$ there is a letter $b$ with arcs from $N_4$ labeled $b$ to two distinct nodes, then these two nodes are eligible for merging. So let us assume that there is no such node $N_4$, viz., $G_i$ is deterministic. Thus, for any node $N$ of $G_i$ and word $w$, the node $\delta (N,w)$ is unique. Where $N_1 ,N_0 ,x$ and $y$ are as in the hypothesis of our theorem, we have $x \neq y$. Let $z_1 ,z_2 , \ldots ,z_q$ be a derivation such that $x = z_1$ and $y = z_q$. By Theorem~2.4, for each $j$, $1 \leq j \leq q$, there is a node $N_j$ such that $z_j \in L_{G_i}(N_j)$. Knowing that $N_1 \neq N_0 = N_q$, we take $h$ to be the smallest positive integer such that $N_h \neq N_{h+1}$. Since $z_h \leftrightarrow z_{h+1}$ and $z_h \neq z_{h+1}$, we have $z_h = sut$ and $z_{h+1} = svt$, where $(u,v)$ or $(v,u)$ is a rule. Put $N'_4 = \delta (e,s)$. Then \[ \delta (N'_4,ut) = N_h \neq N_{h+1} = \delta (N'_4 ,vt) \] Put $N'_1 = \delta (N'_4,u)$ and $N'_2 = \delta (N'_4 ,v)$, so $\delta (N'_1 ,t) = N_h$ and $\delta (N'_2 ,t) = N_{h+1}$. Since $N_h \neq N_{h+1}$, it must be that $N'_1 \neq N'_2$ and the pair $(N'_1 ,N'_2 )$ is eligible for merging.$\Box$ {\bf Corollary.} For $N_1 \neq N_2$, $x \in L_{G_p}(N_1)$ and $y \in L_{G_p}(N_2)$, $x$ and $y$ are not congruent. {\bf Main Theorem.} If $M(P)$ is finite, the elements of the monoid are represented one-to-one by the nodes of the graph $G_p$, from which the multiplication table can be written readily. {\em Proof:\/} Theorem~2.5(1) and the Corollary to Theorem~2.7.$\Box$ It is possible that a generator may turn out to be congruent either to another generator or to $e$. If that happens the monoid can be thought of as having fewer generators than were called for in the presentation. However, general simplification of the generator set is not discussed in this paper. Nor is the problem of whether the monoids of given distinct multiplication tables are isomorphic. {\bf Example 1:} $P = ( \{ b,c \}$, $\{ (bb,b),(cc,c), (bcb,b),(cbc,c),(b^5,c^5) \} )$. The nontrivial equivalence classes for $\equiv _2$ are $\{b,bb \}$ and $\{ c,cc \}$. Since neither $bc$ nor $cb$ is related by $\equiv _2$ to a shorter word, we see that $n_0 > 2$. But the nontrivial equivalence classes for $\equiv _3$ are $\{ b,bb,bbb,bcb \}$, $\{ c,cc,ccc,cbc \}$, $\{ bc,bbc,bcc \}$ and $\{ cb,cbb,ccb \}$. Every word of length~3 is related by $\equiv _3$ to a word of shorter length, so $n_0 = 3$. The graph $G_1$ is given by the following table, in which each monoid element is represented by its minimal word according to the $<$ relation defined above. (The brackets as used in the table of Section~1 are omitted here.) \begin{center} $ \begin{array}{cccccc} & e & b & c & bc & cb \\ b & b & b & cb & b & cb \\ c & c & bc & c & bc & c \end{array} $ \end{center} \noindent Since $\delta (e,b^5) = b$ and $\delta (e,c^5) = c$, the rule $(b^5,c^5)$ allows us to merge nodes $b$ and $c$ to form the new node labeled $b$. We thus get the nondeterministic graph $G_2$: \begin{center} $ \begin{array}{ccccccc} & e & & b & & bc & cb \\ b & b & & b,cb & & b & cb \\ c & b & & b,bc & & bc & b \end{array} $ \end{center} \noindent Next, we merge $b$ and $cb$, getting $G_3$: \begin{center} $ \begin{array}{cccccc} & e & & ~b & & bc \\ b & b & & ~b & & b \\ c & b & & b,bc & & bc \end{array} $ \end{center} \noindent Then we merge $b$ and $bc$, getting $G_4$: \begin{center} $ \begin{array}{cccccc} & e & b \\ b & b & b \\ c & b & b \end{array} $ \end{center} \noindent In $G_4$, $e$ and $b$ are not eligible for merging, so $p = 4$ and the algorithm is concluded. Since the generator $c$ is not mentioned in the table except as a row header (it is congruent to the generator $b$), it can be eliminated from the list of generators. Thus $M(P)$ is isomorphic to the almost trivial monoid $M(P')$ where $P' = ( \{ b \} , \{ (bb,b) \} )$. The next example illustrates that $n_0$ may be arbitrarily large relative to the lengths of the left and right sides of the rules and also relative to the size of $M(P)$: {\bf Example 2:} $P = (\Sigma ,E)$, where, for any fixed integer $q \geq 3$, $\Sigma = \{ 0,b_1 , \ldots ,b_q \}$ and \[ E = \{ (b_i ,b_1 b_2)| \mbox{ all } i \} \cup \{ (b_ib_{i+1},b_ib_{i+1}b_{i+2} ) | 1 \leq i \leq q-2 \} \] \[ \cup \{ (b_{q-1}b_q ,0) \} \cup \{ (b_i0,0),(0b_i ,0),(00,0) | \mbox{ all } i \} \] Note that in $M(P)$, all nonnull words are congruent to $0$, but the derivation of $0$ from any word of length~$1$ requires a word of length $q$. Since longer words are not needed, $n_0 = q$. This in spite of the fact that $M(P)$ has only two elements, $[e]$ and $[0]$, and no rule involves a word longer than $3$. In Section~3 more general things will be said about the size of $n_0$ relative to $P$ and relative to $M(P)$. This section closes with the observation that the Knuth-Bendix completion procedure \cite{kb} can also be used as a semi-algorithm for the problem of whether a given finitely presented monoid is finite. To see this, assume the monoid is finite and consider the function $g$ such that, for every $x \in \Sigma ^*$, $g(x) =$ the smallest word $w$ (in the sense of the $<$ relation defined in this section) such that $w \equiv x$. Where $s$ is the order of the monoid then $|g(x)| \leq s - 1$ for every $x$, by Theorem~1.1. If $R'$ is the set of rules \[ \{ (x,g(x))~|~x \in \Sigma ^*, |x| \leq s, x \neq g(x) \} \] then the Thue system $T = (\Sigma ,R')$ is a presentation for the monoid and is confluent. Thus every finite monoid has a presentation that is a confluent Thue system. (In \cite{kn} it is shown further how to simplify the Thue system to a unique minimal equivalent confluent Thue system.) Hence, if the Knuth-Bendix completion procedure is applied to a presentation of a monoid that happens to be finite (using the length-lexicographic ordering relation), it will terminate with an equivalent presentation that is confluent. However, it will also terminate in certain other cases where the monoid is infinite, again with an equivalent confluent system (with finitely many rules). Fortunately it is easily decided, for any such Thue system $T$, whether $M(T)$ is finite. If so the multiplication table is easily constructed, without need for the procedure of this section. (Since the set $I$ of irreducible strings of a confluent system is regular, whether or not $I$ is finite is easily decided. And $M(T)$ is finite if and only if $I$ is finite. Indeed, the elements of $M(P)$ can be represented by the words of $I$, as is proved in \cite{kn}.) So the Knuth-Bendix completion procedure is a competitor to the procedure of this section. Its advantage is that it can tell us in many interesting instances that the monoid is infinite. \vspace{.5in} {\bf 3. Complexity considerations.} To discuss algorithmic complexity, we must begin with a precise statement of the problem. Actually, there are several ways we could formulate our problem, the most prominent of which is \begin{quote} (P1) Given a presentation and given that the monoid so presented is finite, what is the multiplication table of the monoid? \end{quote} With this formulation the procedure of Section~2 is an algorithm. However, if we omit the second ``given'' phrase, we get a problem that has no algorithm: \begin{quote} (P2) Given a presentation, what is the multiplication table of the monoid presented? \end{quote} The procedure of Section~2 is not an algorithm for (P2) because it will not terminate unless the monoid is finite. (It would appear that (P2) has no algorithm, however we modify our concept of ``multiplication table.'') This observation will help establish some negative complexity results about the problem (P1). The reasoning will be based on the fact that any procedure applied to a presentation, given that the monoid so presented is finite, can also be applied to any presentation whether or not its monoid turns out to be finite. A familiar example of this reasoning will be given in the proof of the next theorem. {\bf Conjecture I.} The problem (P1) is not in any recursive time complexity class. That is to say, for every recursive function $f$ and algorithm $A$ for (P1), there exists a presentation $P$ with $M(P)$ finite, such that the computation of $A$ with input $P$ takes more than $f(|P|)$ time units. ($|P|$ is the length of the written expression for the presentation $P$.) As a credibility argument for this conjecture, a weaker result is now proved. {\bf Definition.} An {\em honest\/} algorithm for (P1) is one that yields, on input $P$, the multiplication table for $M(P)$ in the event that $M(P)$ is finite, but gives no answer at all (either by failing to halt, or by halting with no multiplication table output) in the event that $M(P)$ is infinite. A {\em partially dishonest\/} algorithm for (P1) is one that yields the multiplication table for $M(P)$ when $M(P)$ is finite, but, for at least one $P$ with $M(P)$ infinite, yields some (finite) multiplication table, which of course is spurious. A partially dishonest algorithm is one that is perfectly accurate within the limits of its guarantee, but may give misleading information if as users we go beyond the guarantee by applying it to a presentation $P$ without knowing beforehand that $M(P)$ is finite. In this situation, if the algorithm yields a multiplication table of a finite monoid $M$, we shall be able to conclude only the following: Either $M(P) = M$ or $M(P)$ is infinite. It might be thought that this uncertainty could be resolved by determining whether or not all the rules of $P$ are valid in $M$. If at least one of them is not then from the guarantee we can conclude that $M(P)$ must be infinite. However, if all the rules of $P$ are valid in $M$ we can conclude only that $M$ is a homomorphic image of $M(P)$, which is possibly infinite. Therefore, when we apply a partially dishonest algorithm for Problem~(P1) to a presentation $P$ without having established beforehand that $M(P)$ is finite, we cannot be sure that any multiplication table that is constructed is that of $M(P)$. Note that the procedure of Section~2 is an honest algorithm for problem~(P1). {\bf Theorem 3.1.} Regarding honest algorithms only, the problem (P1) is not in any recursive time complexity class. {\em Proof:\/} Assume there is a recursive function $f$ representing the complexity of some honest algorithm $A$ that solves (P1). This means that from any presentation $P$ of a monoid given to be finite, $A$ constructs the multiplication table for $M(P)$ in at most $f(|P|)$ units of time. Our theorem is proved by proving in the next paragraph that the existence of such a function $f$ would imply the decidability of the following problem: \begin{quote} (P3) Given a presentation, is the monoid so presented finite? \end{quote} This problem is known to be undecidable (see \cite{bo},~pp.~157--160). We assume the existence of the function $f$. Let $P$ be any presentation. Apply $A$ as a procedure to $P$ and stop it, if it has not already stopped, after $f(|P|) +1$ time units. If this run lasts $f(|P|)+ 1$ time units then $M(P)$ is infinite. On the other hand, since $A$ is honest, if $A$ stops of its own accord before $f(|P|) + 1$ time units, then $M(P)$ is finite if a multiplication table is the output, and is infinite if no such table is the output.$\Box$ Another important complexity question remains, which is to relate the time of computation not to the input size but to the output size, which we designate as $s(P)$. We assume that $s(P)$ is a positive integer for every $P$ for which $M(P)$ is finite, but for the purposes of this paper we need not define $s(P)$ precisely. Let $s_0$ be the size of the multiplication table of the trivial monoid, i.e., the monoid whose only element is $e$. We assume that the size of the multiplication table of any other monoid exceeds $s_0$. \newpage {\bf Conjecture II.} There do not exist an algorithm for problem (P1) and a recursive function $f$ such that, for every presentation $P$, the computation time of the algorithm is bounded by $f(s(P))$. That is, for every such algorithm and $f$ there is a $P$ where $M(P)$ is finite but where the computation time exceeds $f(s(P))$. The question is a significant one. No algorithm for a problem can compute in less time than it takes to write the answer; furthermore, it seems fair to allow it to have additional time as a function of the size of the useful output. More generally, it is interesting to investigate the relation of time of computation to output size as an alternative complexity measure. My argument for Conjecture~II begins with two theorems. {\bf Definition:} $n_0(P) =$ the integral value of $n_0$ when the procedure of Section~2 is applied to the presentation $P$. Where $M(P)$ is infinite we write \[ s(P) = n_0(P) = \infty > i \] for every positive integer $i$. Also $f( \infty ) = \infty$ for any function $f$ for which $\lim_{h \rightarrow \infty} f(h) = \infty$. {\bf Theorem 3.2.} It is undecidable for a given positive integer $q$ and presentation $P$ (including those for which $M(P)$ is infinite) (1)~whether $s(P) < q$, and (2)~whether $|M(P)| < q$. {\em Proof:\/} (1)~The following problem is known to be undecidable (see \cite{bo}, pp. 157--159): given $P$, is $M(P)$ the trivial monoid? But this problem is reducible to problem~(1) as follows: Determine whether $s(P) < s_0 + 1$. If so then $M(P)$ is trivial, if~not~not. (2)~Similar to the proof for (1), but using the fact that $|M(P)| < 2$ if and only if $M(P)$ is trivial.$\Box$ {\bf Theorem 3.3.} There is no recursive function $f$ such that $n_0(P) \leq f(s(P))$ for all $P$ such that $M(P)$ is finite. {\em Proof:\/} Assume $f$ exists and, without loss of generality, assume $f(i+1) > f(i)$ for all $i$. With such a recursive function $f$ the undecidable problem of Theorem~3.2(1) could be decided as follows: For the given $P$, begin the procedure of Section~2 (without knowing whether $M(P)$ is finite or infinite). Recall that this procedure has a variable $n$ that runs through the positive integral values of $n$ until $n = n_0$; that $n_0 =$ the smallest $n$ with the property that, for some $k \leq n$, $D(k,n)$ holds; and that this property can be decided effectively for each $n$. In the present application, keep trying successive values of $n$ until one of two possible things happen: Case I: $n = n_0$. Complete the procedure of Section~2, which will enable a decision as to whether $s(P) < q$. Case II: $n = f(q)$. Then, whether or not $M(P)$ is finite, (1)~$n_0(P) \geq f(q)$. Whether or not $M(P)$ is finite, we have (2)~$n_0(P) \leq f(s(P))$: if $M(P)$ is finite (2) follows from the definition of $f$; if infinite, by our convention about $\infty$. From (1) and (2) we get $f(s(P)) \geq f(q)$. Since $f$ is monotonic increasing, $s(P) \geq q. \Box$ The proof of Theorem~3.3 would be a proof of Conjecture~II if the algorithm of Section~2 were the only algorithm for (P1). What prompts me to put forth this conjecture is my feeling that, whatever algorithm might be discovered for (P1), the value of $n_0$ in each application will play an important r\^{o}le in determining the computation time. The undecidability of the word problem for monoids is well known (see, e.g., \cite{bo}, pp.~57ff). Thus there is no effective way of testing whether $x \equiv y$ in $M(P)$, for any given words $x$ and $y$ and interpretation $P$. However, there is an effective way of testing whether $x \equiv_i y$. Section~2 demonstrates that, given $P$, once we know the value of $n_0$ and are prepared to test pairs of words for $\equiv _{n_0}$ we have both the knowledge that $M(P)$ is finite and are able to construct its multiplication table. And it would appear that (1)~before we know the value of $n_0$ we do not even know whether $M(P)$ is finite, and (2)~only by testing words for $\equiv_{n_0}$ can we construct the multiplication table. It therefore is credible that the value of $n_0(P)$ determines in some crucial way the necessary computation time to obtain both the knowledge that $M(P)$ is finite and its multiplication table, whatever algorithm is used. An interesting related question is, given $P$ and words $w_1$ and $w_2$, where $w_1 \equiv w_2$, what is the smallest value of $i$ such that $w_1 \equiv _i w_2$? The following theorem deals with this question, although it does not seem to add credibility to either of the two conjectures of this section. {\bf Theorem 3.4.} There is no recursive function $f$ such that, for any $P$ where $M(P)$ is finite and for any words $w_1$ and $w_2$, \[ w_1 \equiv w_2 \mbox{ if and only if } w_1 \equiv_{f(P,|w_1|,|w_2|)} w_2 \] (Note that this theorem would be easy to prove were it not for the phrase, ``where $M(P)$ is finite.'' In that case we could easily show that the existence of such a recursive function $f$ implies the decidability of the word problem for finitely presented monoids.) {\em Proof:\/} Assume that such a function $f$ exists and, without loss of generality, that $f(P,i,j) < f(P,i,j+1)$ for all $P,i,j$. {\bf Lemma.} The existence of such a function $f$ implies that the following problem is decidable: Given positive integer $r$ and presentation P (including presentations for which $M(P)$ is infinite), is every word of length $r$ congruent in $M(P)$ to a shorter word? {\em Proof of the Lemma:\/} Using the function $f$ we can always compute a tentative answer to this question, disregarding the possibility that $M(P)$ may be infinite. This tentative answer will be valid if $M(P)$ is finite but may not be valid if $M(P)$ is infinite. Suppose first that the tentative answer is ``yes.'' We can enumerate all loop-free derivations from all words of length $r$ in which no word has length exceeding $f(P,r,r-1)$. If we find that there is such a derivation of a shorter word from every word of length $r$ then we know that the correct answer is ``yes.'' On the other hand, if from some word of length $r$ no such derivation yields a shorter word then we know that the tentative ``yes'' answer was not valid and so $M(P)$ is infinite. But $M(P)$ infinite implies that there is a word of every length not congruent to a shorter word; thus the correct answer is ``no.'' \vspace{.1in} If the tentative answer is ``no'' then ``no'' is the correct answer. For if $M(P)$ is finite then the tentative answer is correct. And if $M(P)$ is infinite then it has a word of {\em every\/} length that is not congruent to a word of shorter length and, a fortiori, such a word of length~$r.\Box$ \vspace{.1in} The proof of Theorem~3.4 is completed by using the function $f$ to reduce the problem of the Theorem~3.2(2) (given $P$ and $q$, is $|M(P)| < q$?) to the problem of the Lemma as follows: First use the function $f$ to determine whether or not every word of length $q-1$ is congruent to a shorter word. If so then $M(P)$ is finite; carry through the procedure of Section~2, finding $|M(P)|$ exactly, thus correctly answering the question, is $|M(P)| < q$? \vspace{.1in} If not, i.e., if there is a word $w$ such that $|w| = q-1$ and $w$ is not congruent to a shorter word, then $|M(P)| \geq q$, by Theorem~1.1.$\Box$ \vspace{.1in} Some readers of this section may be disappointed not to see any concrete complexity. In fact, the results of this section indicate that the problem of the paper is beyond concrete complexity. What puts the algorithm of Section~2 beyond practical computation is that the circumstances of its use generally preclude the main advantage of algorithmic computation, namely, the guarantee of a termination and an answer in all instances. In order to have this advantage, users would have to know for some reason that their presentations were those of finite monoids. If they had that information, then probably there would be other available information that could serve to sharpen the procedure to one which could compute within predictable resource limits. It would seem that the theoreticians wanting to extend the results of this paper to complexity-measurable algorithms must be willing to restrict in some way the class of instances to which their algorithms may apply. In other words, they must confine themselves to proper subproblems of the problem~(P1). \newpage \begin{thebibliography}{99} \bibitem{bo} R.V. Book and F. Otto, {\em String-rewriting systems,\/} Springer-Verlag,~1993. \bibitem{kn} D. Kapur and P. Narendran, The Knuth-Bendix completion procedure and Thue systems, {\em SIAM J. Computing,\/} Vol.~14~(1985), pp.~1052--1072. \bibitem{kb} D.E. Knuth and P.B. Bendix, Simple word problems in universal algebras, in {\em Computational problems in abstract algebras\/} (J.~Leech, ed.), Pergammon Press, 1970, pp.~263--297. \bibitem{me} N.S. Mendelsohn, An algorithmic solution for a word problem in group theory, {\em Canadian J. Math.,\/} Vol.~16 (1964), pp~509--516; Correction, Vol.~17 (1965),~p.~505. \bibitem{si} C.C. Sims, {\em Computation with finitely presented groups,\/} Cambridge Univ. Press,~1994. \bibitem{tc} J.A. Todd and H.S.M. Coxeter, A practical method for enumerating cosets of a finite abstract group, {\em Proc. Edinburgh Math. Soc.,\/} Vol.~5 (1936), pp.~26--34. \end{thebibliography} \end{document}