\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{Contributions of Ronald V. Book to the Theory of String-Rewriting Systems\footnote{ This review was written for a celebration of Book's sixtieth birthday, to take place at the University of Minnesota on April 12, 1997. I regret that I could not complete it in time for it to appear in the Festschrift volume (edited by Ding-Zhu Du and Ker-I Ko).}} \author{Robert McNaughton\thanks{Supported by Grant No. CCR-9500182 from the National Science Foundation.} \\ Department of Computer Science \\ Rensselaer Polytechnic Institute \\ Troy, NY 12180-3590, U.S.A. \\ mcnaught@cs.rpi.edu} \date{November, 1996} \maketitle {\bf 1. Introduction.} Ron Book's interest in string-rewriting systems was stimulated by Maurice Nivat \cite{nb}, who, in the 1970's, investigated Thue systems \cite{t} and semi-Thue systems for applications to formal languages and algebra. The collection of research problems that Book was to focus on in the 1980's was, to a large extent, an outgrowth of the collection of problems that Nivat and his collaborators had focused on in the 1970's (see Berstell's 1977 paper \cite{be}). During most of the 1980's Book was intensively interested in research in this area. He is to be lauded for carrying out his research on a broad front, maintaining an interest in several different research questions, developing his own thoughts and paying careful attention to the results of others. He had many research collaborators, including several doctoral students and people who spent some fruitful post-doctoral years at Santa Barbara. He was, in effect, the leader of a group that included all or most of these. Part of our appreciation of the impact that he had on the field of rewriting systems was what these students and post-docs went on to do after they left Santa Barbara. I would like to interject a personal remark at this point and mention how much I have gained from this group. I have profited not only from the clear research orientation that Book has provided, but also from the contact I have had with him and with those who have acquired this orientation from him. Book was joined by Friedrich Otto in 1993 in writing a monograph \cite{&fo} that has a fairly complete account of this area of research, including most of Book's contributions. Because of its importance, I shall often refer to it informally rather than by its location in the list of references at the end of the review. The plan for the remainder of this review is to look at various research questions as Book and his collaborators originally posed them, and, in some cases, to trace their history. Readers who want more technical detail will find most of what they want in the monograph. This short review is not intended to serve either as a complete survey or as a technical introduction. I regret that time has not permitted even a mention of the work of most of his followers. \vspace{.3in} {\bf 2. Thue systems \cite{t} and semi-Thue systems.} These are the two basic abstract concepts used in the study of string rewriting, and are presented here briefly. From them a {\em mixed system\/} is defined, which is a mixture of a Thue system and a semi-Thue system related in a certain way. The concept of {\em mixed system,\/} offered as an explication of the concept of {\em string rewriting system,\/} is not found outside this review; it is used to explain ideas in the evolving literature. A Thue system is an ordered pair $(\Sigma , Q)$, where $\Sigma$ is a finite alphabet and $Q$ is a set of unordered pairs of strings over $\Sigma$. The set $Q$, which is usually finite, is called the ``set of rules.'' For $(y_1 ,y_2 ) \in Q$ 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 are symmetric. One writes $x \leftrightarrow ^* y$ to assert the existence of a sequence $x_0 = x,x_1 , \ldots , x_p = y$ ($p \geq 0$) such that for each $i \leq p-1$, $x_i \leftrightarrow x_{i+1}$. When $x \leftrightarrow ^* y$ holds one says that $x$ and $y$ are {\em equivalent.\/} A {\em semi-Thue system\/} is an ordered pair $(\Sigma ,Q)$ for $\Sigma$ a finite alphabet and $Q$ a set of {\em ordered \/} pairs of strings. Again $Q$ is usually finite, but the rules of $Q$ are not necessarily symmetric. When $(y_1 ,y_2 ) \in Q$ and $x,z \in \Sigma ^*$, one now writes $xy_1z \rightarrow xy_2z$, but not $xy_2z \rightarrow xy_1z$. And one writes $x \rightarrow ^* y$ to assert the existence of a sequence $x_0,x_1, \ldots x_p$ ($p \geq 0$) such that, for each $i \leq p-1$, $x_i \rightarrow x_{i+1}$. When $x \rightarrow ^* y$ holds one says various things, e.g., ``$y$ is derivable from $x$'' and ``$x$ reduces to $y$.'' A string-rewriting system frequently involves a semi-Thue system; $x \rightarrow y$ means ``$x$ is (or can be) rewritten as $y$.'' But rewriting in practice is mostly of two kinds, reduction and generation. If $x \rightarrow y$ is a reduction then $y$ is somehow simpler or smaller than $x$, e.g., $|y| < |x|$. If it is generative then $y$ is generally more complex or larger than $x$, e.g., $|y| > |x|$. (The notation $|x|$ means the length of the string $x$.) In the rewriting literature, $x \rightarrow y$ frequently means ``$x$ reduces to $y$ in one step.'' In Book's papers, it frequently implies that $|y| < |x|$, and sometimes merely that $|y| \leq |x|$. Thue systems are important as presentations of monoids, in which the derivation of an equivalence $x \leftrightarrow ^* y$ is a proof that $x$ and $y$ represent the same object in the monoid. Thus Thue systems are in essence the basis of combinatorial monoid theory (of which combinatorial group theory is a well known subtheory). A {\em mixed system\/} is an ordered triple $(\Sigma , E,R)$ in which $(\Sigma ,E)$ is a Thue system, $(\Sigma ,R)$ is a semi-Thue system, and (defining $\leftrightarrow$ from $E$ and $\rightarrow$ from $R$ as above) $x \rightarrow y$ implies $x \leftrightarrow ^* y$. In a mixed system, $\leftrightarrow ^*$ is called the {\em equivalence relation\/} and $\rightarrow ^*$ the {\em reduction relation.\/} The relation $\leftrightarrow$ is called the {\em equivalence-step relation\/} and $\rightarrow$ the {\em reduction-step relation.\/} A certain kind of mixed system predominated in Book's papers in the 1980's (although he did not refer to it as a ``mixed system''). This system begins as a Thue system $(\Sigma ,E)$ from which the relations $\leftrightarrow$ and $\leftrightarrow ^*$ are defined. Then, from it, a semi-Thue system is defined as $(\Sigma ,R)$ where $R$ is the set of all $(y_1 ,y_2)$ where $|y_2| < |y_1|$ and either $(y_1 ,y_2 ) \in E$ or $(y_2,y_1) \in E$, with $\rightarrow$ and $\rightarrow ^*$ defined as above. Verbally, $\rightarrow ^*$ is the {\em reduction relation based on length.\/} The relationship between $\leftrightarrow$ and $\rightarrow$ in this system may be complicated by the presence of length-preserving rules in $E$, i.e., rules $(y_1,y_2) \in E$ such that $|y_1| = |y_2|$. Another kind of mixed system begins with what is called an {\em abstract reduction system\/} in the recent literature, which is a semi-Thue system $(\Sigma ,R)$ whose $\rightarrow$ (as defined) is to be thought of as a reduction-step relation. Some semi-Thue systems are more appropriate for being thought of as reduction systems than others. For example, it is generally assumed that the reduction-step relation should be {\em noetherian;\/} that is, there should be no infinite sequence of strings $x_1,x_2, \ldots$ such that $x_i \rightarrow x_{i+1}$ holds for all~$i$. One implication of this property is that we can never have both $x \rightarrow y$ and $y \rightarrow x$. Another implication is the existence of at least one {\em irreducible\/} string, i.e., an $x \in \Sigma ^*$ for which there is no $y$ such that $x \rightarrow y$. Therefore, if $\rightarrow$ is appropriate for being a reduction-step relation then the relation $\rightarrow ^*$ is a transitive, reflexive, antisymmetric relation, whose converse is a partial well ordering. We can get a mixed system from such an existing semi-Thue system $(\Sigma ,R)$ by putting $E = \{(x,y)|(x,y) \in R \mbox{ or } (y,x) \in R \}$. This type of mixed system is, in effect, what was used in a 1988 monograph by Jantzen \cite{j} and in the very first chapter of the 1993 monograph by Book and Otto. More will be said about it in the next section. In this review, a rewriting system will always be a mixed system. In some cases we can think of equivalence as coming first and reduction as an instrument in proving equivalence. In other cases we can think of reduction as coming first and equivalence as being defined from it. \vspace{.3in} {\bf 3. The Church-Rosser property.} This was the most eminent of the properties of Thue systems that Book studied. But the concept as Book used it in the early 1980's is not precisely the same as the concept as it usually appears now. The earlier concept is based on the length of strings, the later one is more abstract. In this review both concepts will be subsumed under one. A mixed system $(\Sigma ,E,R)$ has the {\em Church-Rosser property\/} if, for every $x \in \Sigma ^*$, there is a sequence $x_0,x_1 , \ldots ,x_n,~n \geq 0$, such that (1) $x_0 = x$, (2) $x_i \rightarrow x_{i+1}$ for each $i$, and (3) $x_n$ is the unique irreducible string equivalent to $x$. The string $x_n$ is thus a {\em canonical form\/} of $x$. The sequence $x_0 ,x_1 , \ldots ,x_n$ we call a {\em reduction sequence\/} for $x$. (The term ``Church-Rosser'' honors work by Alonzo Church and Barkley Rosser \cite{cr} on the lambda calculus.) Note that if we have $x = x_0 \rightarrow x_1 \rightarrow \cdots \rightarrow x_i$, and both $x_i \rightarrow x_{i+1}$ and $x_i \rightarrow x'_{i+1}$ hold, then we can take either $x_{i+1}$ or $x'_{i+1}$ as the $(i+1)^{st}$ string in a reduction sequence for $x$. The two strings $x_{i+1}$ and $x'_{i+1}$, being equivalent to $x$, have the same canonical form as $x$, which implies that there are reduction sequences to it both from $x_{i+1}$ and from $x'_{i+1}$. Consequently, whenever we are constructing a reduction sequence from a given string, we can always take as the next string any string to which the last string reduces. Thus a reduction sequence from any $x$ can be obtained in a straightforward way, with no need for back-tracking. A mixed system $(\Sigma ,E,R)$ has the {\em length-based Church-Rosser property,\/} if it has the Church-Rosser property and reduction is always accompanied by a decrease in length, viz., $(x,y) \in R$ implies $|y| < |x|$, and hence $x \rightarrow y$ implies $|y| < |x|$. In such a system, the reduction of a string to its canonical form is expeditious for two reasons: not only is backtracking avoidable in obtaining the reduction sequence, as already noted, but each new string in the sequence is shorter in length than its predecessor. Thus the reduction of a string to its canonical form in a system with the length-based Church-Rosser property can be done in linear time (as will be demonstrated in detail in the next section). Book made much of this fact. Book was also impressed with the fact that it was computationally simple to tell whether a given Thue system $(\Sigma ,Q)$ for finite $Q$ has the length-based Church-Rosser property. With O'Dunlaing \cite{&od} he noted that the decision procedure for this problem, discovered by Nivat and Cochet \cite{nb}, could be made to run in polynomial time. When length-preserving rules play an important r\^{o}le, it may be appropriate to consider a property that is considerably weaker than the length-based Church-Rosser property. A rewriting system is {\em preperfect\/} if it satisfies two conditions: \begin{quote} (a) For every $x \in \Sigma ^*$, there is a sequence $x_0 = x,x_1 , \ldots ,x_n$ such that ~$x_i \leftrightarrow x_{i+1}$ and ~$|x_{i+1}| \leq |x_i|$ for every $i$, and ~$x_n$ has minimal length of all strings equivalent to $x$ (but may not be uniquely so). (b) For $x,y \in \Sigma ^*$, if $|x| = |y|$, $x \leftrightarrow ^* y$ and $x$ and $y$ have minimal length in their equivalence class, then there exist $n \geq 0$ and a sequence of equal-length strings $x_0 = x,x_1, \ldots ,x_n = y$ such that $x_i \leftrightarrow x_{i+1}$ for each $i$. \end{quote} This definition varies from the one Book gives, but is equivalent to it. Note that there is no reference in the definition to a reduction relation. Book and his collaborators did not investigate or use the preperfect property as much as they did the length-based Church-Rosser property. There is a similarity and a difference between preperfectness and the length-based Church-Rosser property. Systems of both kinds offer the computational advantage that any given string can be reduced to an equivalent string of minimal length. However, the reduction is more expeditious if the system has the length-based Church-Rosser property. In general, the algorithm to reduce a given string to its minimal length in preperfect systems is computationally more complex. The procedure to reduce a string to an equivalent string of minimal length in a system is useful in the solution of the {\em string equivalence problem\/} for that system, i.e.: given strings $w_1$ and $w_2$, is $w_1 \leftrightarrow ^* w_2$? (This problem is also known as the {\em word problem\/} for the monoid presented by the Thue system.) To decide whether $w_1$ and $w_2$ are equivalent, one simply reduces the strings to their canonical forms and tests for equivalence. The string equivalence problem for Church-Rosser systems and preperfect systems is therefore solvable. However, the algorithm is more complex for preperfect systems than for Church-Rosser systems. As we have noted, even the procedure for obtaining a minimal-length string equivalent to a given string is more complex for preperfect systems. For Book's discussion of alternatives to the length-based Church-Rosser property for systems with viable reduction procedures, the reader is referred to pp. 65--66 of \cite{87}. In cases where a system does not have the length-based Church-Rosser property, it is sometimes possible to revise the system so that it has some other Church-Rosser property. Usually this would require finding another reduction relation not based wholly on length. One idea along these lines is to refine the ``shorter than'' relation over strings to include alphabetic comparisons. Assuming the alphabet $\Sigma$ is ordered, we can define $x < y$ for $x,y \in \Sigma ^*$ to mean that either $|x| < |y|$ or $|x| = |y|$ and $x$ precedes $y$ in alphabetic order. Then, following \cite{kn}, we can define a mixed system $(\Sigma ,E,R)$ to be {\em lexicographically confluent\/} if (1)~$x < y$ for all $(y,x) \in R$ and (2)~$(\Sigma ,E,R)$ has the Church-Rosser property. The value of this idea rests on the fact that $<$ is a {\em complete ordering\/} of $\Sigma ^*$: we always have either $x< y$ or $y < x$, for distinct strings $x$ and $y$. Thus there are variants to the length-based Church-Rosser property, which is the reason the definition offered at the beginning of this section does not involve length at all. That definition is a generalization of the length-based concept, which Book most often used in the 1980's. However, in their 1993 monograph, Book and Otto have put the abstract concept in the very first chapter, not discussing the length-based concept until Chapter 3 (where, however, it is studied quite thoroughly). In the mathematical sciences, abstract concepts are often preferred to concrete concepts because they are more general. Let us make some observations along this line about Church-Rosser rewriting systems before closing this section. If a mixed system $S_1 = (\Sigma ,E,R)$ has the Church-Rosser property then it is possible to define \[ E' = \{(x,y)|(x,y) \in R \mbox{ or } (y,x) \in R \} \] whereupon the system $S_2 = (\Sigma ,E',R)$ is equivalent to $S_1$; that is to say, $x \leftrightarrow ^* y$ holds in $S_1$ if and only if $x \leftrightarrow ^* y$ holds in $S_2$. (The proof is left to the reader.) This shows that any mixed system with the Church-Rosser property could have started out as an abstract reduction system, and explains in part the motivation behind the use of abstract reduction systems in recent rewriting theory. Theorists who prefer to work with abstract reduction systems like to focus on the {\em confluence\/} property of such systems. Where $(\Sigma ,R)$ is an abstract reduction system and $E$ is defined from $R$ as $E'$ was defined in the preceding paragraph, then $(\Sigma ,R)$ has the confluence property if and only if $(\Sigma ,E,R)$ has the Church-Rosser property (see, e.g., Lemma 1.1.7 of \cite{&fo}). For the purposes of this paragraph this result can serve as a definition of ``confluence.'' Because of the closeness in meaning of ``confluence'' and ``Church-Rosser,'' the former term is not discussed in this review outside this paragraph, even though it is at present the more popular term. In the next section we shall return to the more concrete Church-Rosser concept of the early 1980's in order to describe one of Book's most important ideas. \vspace{.3in} {\bf 4. Linear-time string reduction.} Perhaps the most impressive of Book's results about rewriting systems from an applications point of view is that systems with the length-based Church-Rosser property have a highly efficient method of reduction of a string to a canonical form. In \cite{jacm} he shows how to construct, for any such system, an automaton with two pushdown stores that can reduce any string over the alphabet to its canonical form in time that is linear in the length of the string. This method of reduction will now be described in detail, although the treatment will be discursive rather than technical. We assume that we have a mixed system $(\Sigma ,E,R)$ with the length-based Church-Rosser property. To execute the first reduction step of a given string, we must find a factor of that string that is the left member of a rule of $R$; such a factor let us call a ``handle.'' There may be several handles in the string, so we must decide both how we should begin our search for handles and which handle should be the first to be rewritten. We might locate all the handles, and chose to reduce according to which rule yields the greatest reduction in length. But it turns out that it would be quite uneconomical of time to locate all possible handles before each new step in the reduction. It could in many cases result in a reduction with a small number of reduction steps, but each step would require much time in deciding which is the optimal handle to rewrite. Let us give up on this idea. Instead, let us reduce as soon as we find the first handle. Arbitrarily, we can search from left to right, and rewrite the first handle we find. Having completed the reduction step we can then do the same thing to the new shorter string, and so on. In this manner we shall at each new step be reducing the string that results from the previous step by rewriting its leftmost handle. Eventually we shall come to a string without a handle, at which point the reduction is complete: the final string is an irreducible equivalent of the original string. And, since the system has the Church-Rosser property, it is the only irreducible equivalent string. But there is another point of efficiency to be gained. Suppose in a given step of the procedure that we have reduced $w_1xw_2$ to $w_1yw_2$, where $(x,y) \in R$, and where $w_1$ is long. In order to find the leftmost handle in $w_1yw_2$, we do not have to begin our search at the left end of $w_1$. We can be sure from what has happened so far that $w_1$ has no handle. (We omit the proof of this fact, which is by mathematical induction on the number of reduction steps that have taken place.) More precisely, let $h$ be the length of the longest left side of a rule of $R$ minus $1$. If $|w_1| > h$ then, taking $w_1 = w_{12}w_{13}$ where $|w_{13}| = h$, we can confine our search to $w_{13}yw_2$, ignoring $w_{12}$ completely for this step. If $|w_1| \leq h$ then, of course, we must begin our search at the left end of $w_1$. This completes our description of the algorithm, from which it can be proved that it will always result in the unique irreducible string equivalent to the original, provided that the system has the Church-Rosser property. Everything that has been said so far about the algorithm holds even if the Church-Rosser property is not the length-based property. However, the analysis that follows, showing that it is a linear-time algorithm, requires the length-based property. If the system is not Church-Rosser at all, an equivalent irreducible string will be found, but there is no guarantee that it will be unique or have minimal length. In order to analyze the algorithm it is convenient to modify the notion of ``step.'' Let us stipulate that the algorithm begins at time 0 with a pointer at the leftmost character of the input string. Thereafter, the string will be modified and the pointer will be moved. At any time $t$, when $t$ steps have been executed, let $w_1(t)w_2(t)$ be the string, $w_2(t)$ being the suffix that begins with the character that has the pointer. Thus at time 0, $w_1(0)$ is null and $w_2(0)$ is the entire input string. The strings $w_1(t+1)$ and $w_2(t+1)$ are obtained from $w_1(t)$ and $w_2(t)$ as follows: Between time~$t$ and time~$t+1$, the rules of $R$ are considered in order, selecting the first one whose left member is a prefix of $w_2(t)$. (For the analysis we need not specify how the rules of $R$ are to be ordered, although some orderings might have small gains in efficiency over others.) If such a rule is found, that handle is rewritten according to that rule and the pointer is moved $h$ places to the left on the string, or, to the beginning of the string if that is not possible. Thus if $w_1(t) = z_1z_2$ and $w_2(t) = x_1x_2$, where $|z_2| = min(|w_1(t)|,h)$ and the rule is $(x_1,y)$, then $w_1(t+1) = z_1$ and $w_2(t+1) = z_2yx_2$. If this action occurs the step is called a {\em step of type~1.\/} If there is no rule whose left member is a prefix of $w_2(t)$ then the pointer is moved one place to the right; if this action occurs the step is called a {\em step of type~2.\/} The algorithm ends when $|w_2(t)|$ is smaller than the length of the shortest left member of a rule. Note that the amount of time for each step is limited by a constant depending only on the system itself. Thus it can be proved that the execution time for the algorithm is bounded by a linear function of the length $g$ of the original string, by proving that the number of steps is so bounded. Accordingly, let $k_1$ ($k_2$) be the number of steps of type~1 (type~2) in the execution of the algorithm. Since $|y| < |x|$ for all $(x,y) \in R$, the length of the string, which never increases, is diminished at least by $1$ for each step of type~1. Consequently, $k_1 < g$. The pointer, during the course of the computation, moves across almost the entire string. During a step of type~1 it moves left at most $h$ characters, $h$ being a constant for the system. During a step of type~2 it moves right one character. Where $r =$ the total net movement rightward in the course of the algorithm, we have $k_2 - hk_1 \leq r < g$, and hence $k_2 < g +hk_1 < (1 + h)g$. This gives us an upper bound on the total number of steps: \[ k_1 + k_2 < k_1 + (1+h)g < (2 + h)g \] And so we are able to conclude that the computation time for the algorithm is bounded by a linear function of $g$. This algorithm would be easily implemented as a computer program, which, if care is taken in the writing, runs in linear time. In \cite{jacm}, Book chose to implement the algorithm as a pushdown automaton with two pushdown stores (see also the proof of Theorem~2.2.9 in \cite{&fo}). \vspace{.3in} {\bf 5. Monoid presentation.} As mentioned in Section~2, a Thue system $(\Sigma ,E)$ in which $E$ (as well as $\Sigma$) is finite can be regarded as a finite presentation of a monoid, where $\Sigma$ is the set of generators and $E$ is the set of relators. (The relators in a monoid presentation are unlike the relators in a group presentation, in that they cannot always be reduced to the form $(w,e)$, where $w$ is a word over $\Sigma$ and $e$ is the null word representing the monoid or group identity.) Thus various questions about monoids can be identified with questions about Thue systems. Book sought results about combinatorial monoid theory that could be obtained by a study of rewriting systems. A good example is the string equivalence problem for Thue systems, discussed in Section~3. It is well known that this problem, whose domain covers all Thue systems, is undecidable. An important subproblem of the string equivalence problem is the {\em nullifiability\/} problem: given a Thue system $T = (\Sigma ,E)$ and $w \in \Sigma ^*$, does $w \leftrightarrow ^* e$ hold in $T$? (The symbol $e$ represents the null string, which represents the monoid identity.) This problem is also undecidable. There are many problems about Thue systems that are unsolvable when the domain is the class of all Thue systems. One of Book's research objectives has been to find interesting subclasses of the class of all Thue systems for which these problems are decidable. He achieved certain results along these lines in the early 1980's, on which Otto made improvements in 1986 (\cite{o1}, \cite{o2}). Two such problems are: (1)~The {\em free-monoid problem:\/} does a given Thue system represent a free monoid (or, if you prefer, a monoid isomorphic to a free monoid)? (2)~The {\em group problem:\/} does a given Thue system represent a group (or a monoid isomorphic to a group)? Of course, every free monoid can be represented in a way that makes it apparent that it is a free monoid: if it has $n$ generators, take $(\Sigma ,E)$ where $\Sigma = \{ a_1 , \ldots ,a_n \}$ and $E$ is the empty set. The same holds for groups: if the group has $n$ generators take $\Sigma = \{ a_1 ,a'_1 , \ldots ,a_n ,a'_n \}$ and $E = E_1 \cup E_2$ where \[ E_1 = \{ (a_1a'_1 ,e),(a'_1a_1 ,e), \ldots ,(a_na'_n ,e), (a'_na_n ,e) \} \] and $E_2$ is the set of group relators expressed appropriately. The free-monoid problem and the group problem are undecidable for the class of all Thue systems because the free-monoid structure and the group structure can be disguised. Book used the Church-Rosser property and another property, known as the {\em monadic\/} property, to define subclasses of the class of Thue systems for which the free-monoid problem and the group problem are solvable. A Thue system $(\Sigma ,E)$ is {\em monadic\/} if, for every rule $(u,v) \in E$, $|v| \leq 1$ and $|u| > |v|$. The utility of this concept was that it provided access to the theory of context-free grammars and the theory of regular grammars, which have decidability results that can sometimes be applied to monadic Thue systems. Although Book often had in mind the length-based Church-Rosser property, the results discussed in this section are valid for the more general Church-Rosser property. Book was able to prove in 1983 that the free-monoid problem was decidable for the class of all monadic Church-Rosser Thue systems with the cancellative property. (A Thue system has the {\em cancellative property\/} if, for all $x,y,z \in \Sigma ^*$, $xz \leftrightarrow ^* yz$ implies $x \leftrightarrow ^* y$, and $zx \leftrightarrow ^* zy$ implies $x \leftrightarrow ^* y$.) This result, although not stated in \cite{83}, follows by methods used in that paper (see p. 172 of \cite{&fo}). Otto's improvement on this result \cite{o1} implies that the free-monoid problem is decidable for the class of Church-Rosser Thue systems $(\Sigma ,E)$ where $E$ is finite. In 1982 Book proved \cite{82b} that the group problem is decidable for the class of monadic Thue systems with the Church-Rosser property (cancellativity was not needed). Otto's improvement \cite{o2} implies that this result (as in the case of the free-monoid problem) holds when the class of Thue systems is the class of Church-Rosser Thue systems $(\Sigma ,E)$ with finite $E$. The last chapter of the monograph by Book and Otto gives a complete and well written technical exposition of the problems discussed in this section. The end of that chapter surveys a number of other algebraic problems about Thue systems: the conjugacy problem, the cancellativity problem, and the problem of the existence of a nontrivial idempotent, which are not discussed here. \vspace{.3in} {\bf 6. Another of Book's results about monoids \cite{84}.} This last section will consider another problem about the monoids represented by Thue systems. An element of such a monoid can be thought of as an equivalence class of strings. Since the equivalence classes can be multiplied to get other equivalence classes, they are called {\em congruence classes\/}. A congruence class can be identified by any of its members; the notation $[x]$, which for any $x \in \Sigma ^*$ represents the set of all strings congruent to $x$, can be used conveniently to represent the elements of the monoid. In the monoid of every Thue system, $[e]$ is the monoid identity ($e$ being the null string). A concept of interest to Book was the {\em group of units\/} of a monoid, i.e., the largest subgroup of the monoid whose identity is the identity of the monoid. The elements of this subgroup are called the {\em units\/} of the monoid. A unit can be identified as the congruence class of any element that has both a left inverse and a right inverse with respect to the monoid identity. Book was interested in the various properties of monoids that could be discerned from their groups of units, including the question about whether or not a monoid presentation had the length-based Church-Rosser property. He managed to give a complete solution to this problem for monoids defined by a Thue system $(\Sigma ,E)$ in which $E$ has just one rule of the form $(w,e)$, $w \in \Sigma \Sigma ^*$. His result broke down into four cases depending on the string $w$. He used the following concepts from a field of study known as ``the combinatorics on words'': The {\em root\/} of the string $w$ is the shortest string $x$ such that $w = x^k$ for some positive integer $k$. If $w$ is its own root ($k = 1$) then $w$ is {\em primitive.\/} If there are nonnull strings $u,v,z$ such that $w = uz = zv$ then $z$ is an {\em overlap\/} of $w$. Book's result \cite{84} (see also pp. 62--63 of \cite{87}) about a Thue system $T = (\Sigma , \{ (w,e) \})$, the monoid $M_T$ presented by $T$ and the group $U_T$ of units of $M_T$ states: \begin{quote} (a) If $w$ is primitive and has no overlap then $U_T$ is trivial (meaning that $[e]$ is the only member of $U_T$), and $T$ has the length-based Church-Rosser property. (b) If the root of $w$ is $x$, $w = x^k$ for some $k \geq 2$, and $x$ has no overlap then $U_T$ is a nontrivial finite cyclic group of order $k$, and $T$ has the length-based Church-Rosser property. (c) If $w$ is primitive and has overlap then $U_T$ is infinite and $T$ does not have the length-based Church-Rosser property. (d) If $w$ is not primitive and its root has overlap then $T$ does not have the length-based Church-Rosser property and $U_T$ is infinite with a nontrivial finite cyclic subgroup. \end{quote} {\bf Example for Case~(b):} Let $T = ( \{ a,b \} , \{ (ababab,e) \} )$. Then $w = (ab)^3$ has root $ab$, which has no overlap. Using well known methods (see, e.g., \cite{&od}), it is easy to see that $T$ has the length-based Church-Rosser property with the one reduction rule $(ababab,e)$. It is not difficult to see that $[ab], [abab], [e] \in U_T$ and that no two of these three are equal. It is somewhat more difficult to verify that these three are the only elements of $U_T$, and that, therefore, $U_T$ is a cyclic group of order~$3$. (One way of carrying through this verification is to prove that any reduced string that is not $e$ or $ab$ or $abab$ has one of the following forms: (1)~$(ab)^ibu$ ($0 \leq i \leq 2$, $u \in \Sigma ^*$), in which case it has no right inverse; (2)~$ua(ab)^i$ ($0 \leq i \leq 2$, $u \in \Sigma ^*$), in which case it has no left inverse; or (3)~$(ab)^i aaubb(ab)^j$ ($0 \leq i \leq 2$, $0 \leq j \leq 2$, $u \in \Sigma ^*$), in which case it has neither a left inverse nor a right inverse.) {\bf Example for Case~(c):} Let $T = ( \{a,b \} , \{ (abbab,e) \})$. Then $w = abbab$ is primitive and has the overlap $ab$. First note that $ab$ and $b$ commute: \[ abb \leftrightarrow abbabbab \leftrightarrow bab \] Hence $babab$, $abbab$, $ababb$ and $e$ are all equivalent in $T$. From this we see that $[b]$ has the two-sided inverse $[abab]$ in $M_T$. Thus $[b] \in U_T$, and $[b^i] \in U_T$ for all $i \geq 0$. Observe that, for $x_1,x_2 \in \Sigma ^*$, if $x_1 \leftrightarrow ^* x_2$ then, for some integer $k$, $|x_1| - |x_2| = 5k$, $|x_1|_a - |x_2|_a = 2k$ and $|x_1|_b - |x_2|_b = 3k$. (The notation $|x_1|_a$ means the number of occurrences of the letter $a$ in the string $x_1$, etc.) From this it follows that, for $i \neq j$, $b^i$ and $b^j$ are not equivalent, and hence $[b^i] \neq [b^j ]$ in $U_T$; thus $U_T$ is infinite. It also follows that $abb$ and $bab$, which are equivalent in $T$, are not equivalent to any shorter string; thus $T$ does not have the length-based Church-Rosser property. The reader is warned that the the proofs of Cases~(b) and~(c) of Book's theorem are considerably more involved than the proofs sketched above for the two examples. Book was interested in the question about what could be done and what could not be done by Church-Rosser rewriting systems. The theorem examined in this section turns out to be helpful in answering this question in certain cases. For Book's detailed discussion of this matter, see pp.~62--64 of \cite{87}. This ends my brief and incomplete review of Ron Book's work on rewriting systems during the 1980's. Since I have not attempted to cover all of his accomplishments in the area, and have not given an account of the results of his disciples, I can claim to have described only a small part of his impact on the theory of rewriting systems. \vspace{.3in} \begin{thebibliography}{99} \bibitem{be} J. Berstel, Congruences plus que parfaites et langages alg\'{e}briques, {\em Seminaire d'Informatique Th\'{e}orique,\/} Institute de Programmation (1976--77), pp.~ 123--147. \bibitem{jacm} R. Book, Confluent and other types of Thue systems, {\em J. Association Computing Machinery,\/} Vol.~29~(1982), pp.~171--182. \bibitem{82b} R. Book, When is a monoid a group? The Church-Rosser case is tractable, {\em Theoretical Computer Science,\/} Vol.~18~(1982), pp.~325--331. \bibitem{83} R. Book, Decidable sentences of Church-Rosser congruences, {\em Theoretical Computer Science,\/} Vol.~24~(1983), pp.~301--312. \bibitem{84} R. Book, Homogeneous Thue systems and the Church-Rosser property, {\em Discrete Mathematics,\/} Vol.~48~(l984), pp.~137--145. \bibitem{87} R. Book, Thue systems as rewriting systems, {\em J. Symbolic Computation,\/} Vol.~3~(1987), pp.~39--68. \bibitem{&od} R. Book and C.\'{O}'Dunlaing, Testing for the Church-Rosser property, {\em Theoretical Computer Science,\/} Vol.~16~(1981), pp.~223--229. \bibitem{&fo} R. Book and F. Otto, {\em String-rewriting systems,\/} Springer-Verlag, 1993. \bibitem{cr} A. Church and J.B. Rosser, Some properties of conversion, {\em Trans. Am. Math. Soc.,\/} Vol.~39~(1939), pp.~472--482. \bibitem{j} M. Jantzen, {\em Confluent string rewriting,\/} EATCS Monograph No.~14, Springer-Verlag, 1988. \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{nb} M. Nivat and M. Benois, Congruences parfaites et quasi-parfaites, {\em Seminaire Dubreil,\/} Vol. 25~(1971--72), 7--01--09. \bibitem{o1} F. Otto, Church-Rosser Thue systems that present free monoids, {\em SIAM J. Computing,\/} Vol.~15~(1986), pp.~786--792. \bibitem{o2} F. Otto, On deciding whether a monoid is a free monoid or is a group, {\em Acta Informatica,\/} Vol.~23~(1986), pp.~99-110. \bibitem{t} A. Thue, Probleme \"{u}ber Ver\"{a}nderungen von Zeichenreihen nach gegebenen Regeln, {\em Skr. Vid. Kristiania, I Mat. Natuv. Klasse,\/} No.~10~(1914), 34~pp. \end{thebibliography} \end{document}