Otto considers regularity-preserving properties of string- and term-rewriting systems. The main result is that regularity is preserved by string-rewriting systems (SRSs) when the underlying alphabet is extended by adding letters which, by definition, do not occur in the rules of the SRS. (As usual, the notion of regularity equates with the ability to recognize a related language by a finite-state acceptor.) This is interesting but, as is also shown in the paper, it is undecidable in general whether a given SRS preserves regularity, and certain “restricted” problems are still open. Using appropriate simulation mappings, the author then derives analogous results associated with Turing machines.

This is a well-written technical paper in which the proofs of many of the positive results are constructive in nature. Poor line breaks (breaking mathematical expressions in ways convenient to the typesetter but not the reader or, I suspect, the author) save very little space in a paper of this size. Several pieces of notation (and terminology) are not directly defined, and readers will have to deduce their meanings from the surrounding text. Finally, notwithstanding the mathematician’s fiercely defended right to invent and use any notation he or she wishes, the use of “:=” to indicate definition rather than employing definitional equals must be questioned. It clashes with mainstream computer science, where “:=” usually denotes the association of a name with a value only until it is bound to a new value--and that such a change is anticipated.