Died: 28 May 1997 in Santa Barbara, California, USA

**Ron Book** was born and grew up in a farming community. He attended Grinnell College, a private institution of higher education in Grinnell, Iowa, and was awarded a B.A. by the College in 1958. He then studied at the Wesleyan University, a private, institution of higher education in Middletown, Connecticut, and was awarded an M.A. in Teaching in 1960 and a second M.A. in 1964. He undertook research at Harvard University under the supervision of Sheila A Greibach and was awarded a Ph.D. in 1969 for his thesis *Grammars with Time Functions*. In 1970 Book and Greibach published *Quasi-realtime languages* and they described the contents of the paper as follows:-

The quasi-realtime languages are seen to be the languages accepted by nondeterministic multitape Turing machines in real time. The family of quasi-realtime languages forms an abstract family of languages closed under intersection, linear erasing, and reversal. It is identical with the family of languages accepted by non-deterministic multitape Turing machines in linear time. Every quasi-realtime language can be accepted in real time by a nondeterministic one stack, one pushdown store machine, and can be expressed as the length-preserving homomorphic image of the intersection of three context-free languages.

Another early work by Book on languages was the paper *On languages accepted in polynomial time* which he published in 1972. It shows that several different languages are distinct. These are the family of languages accepted by non-deterministic Turing machines in polynomial time, the corresponding family for deterministic Turing machines, the family of context-sensitive languages, the family of languages accepted by deterministic linear bounded automata, and the set of languages accepted by deterministic Turing machines in exponential time. A survey of where the theory of formal languages stood in 1972 was presented by Book in *Topics in formal language theory*. His own description of the contents of this survey are as follows:-

In Section2, examples are given to explain the notion of finite specification of languages and the Chomsky hierarchy is defined. In Sections3through5, several sets of questions are discussed with answers phrased in terms of the Chomsky hierarchy. Some of the results on context-free languages are stated in Section6, and extensions of context-free languages are sketched in7. In Section8, some questions on context-sensitive grammars are discussed, and in Section9, complexity classes of formal languages are studied. Section10contains a description of the metatheory and Section11highlights work still to be done.

Book was appointed to Harvard and later he moved to Yale. Maurice Nivat writes in [8] about his first meeting with Book:-

We met in1971in the University of Western Ontario, in London, Ontario, at the occasion of some sort of summer school on Language Theory. I spent six weeks there with my wife and three children who were at that time11, 8and4. In one day this friendship was established not only between Ron and me but also between Ron and my wife, between Ron and each of my three children. We did some work together ... mainly during a summer Ron spent in France, mostly in a small village of300inhabitants where I bought an old farm house in1973. Twenty-five years later some people from this village are still remembering this smiling American who did not speak French but who succeeded with his hands and with his smiles, smiles in his eyes, smiles on his mouth, smiles all over his face, to communicate with them, to share with them his energy, his joy of life. Ron indeed liked this place ... he liked talking to the farmers there. ...[He]did not like large towns, he did not like the sophistication of the traditional elite, he liked simple people working day after day to grow crops.

In 1977 Book was appointed Professor of Mathematics at the University of California at Santa Barbara. His research turned more towards string-rewriting systems, and monoid presentations. For example in 1981 he published *Thue congruences and the Church-Rosser property* which studied the relationship between finite Thue systems and the semigroups which they present. In the following year Book published *When is a monoid a group? The Church-Rosser case is tractable* which shows that there is a polynomial-time algorithm for deciding whether a finite monadic Church-Rosser Thue system defines a group.

McNaughton writes in [7]:-

During most of the1980s Book was intensively interested in[string-rewriting systems]. 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.

The main results which Book proved on rewriting systems are contained in his important book *String-rewriting systems* (1993) on which he collaborated with Fred Otto.

However Book worked on other topics at the same time as he studied rewriting systems. D-Z Du and K-I Ko write in [3]:-

In complexity theory, Book made central contributions to a wide variety of subareas. He initiated research on restrictive relativizations in the early1980s and investigated intensively the effect of different types of oracles on the computational power of oracle machines. This work has strongly influenced the direction of research in relativization. He was among the first to recognise the importance of tally sets, sparse sets, and other sets of succinct descriptions. He originated studies of lowness of sparse sets, of characterizations of sparse sets by Kolmogorov complexity, and of reducibility and equivalence to sparse sets.

In all Book published over 150 articles on algebra and theoretical computer science. However he contributed in many other ways in addition to his research. In 1970-71 he was a member of the Executive Committee of SIGACT (Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory), he was Chairman of the Institute of Electrical and Electronics Engineers Technological Committee on Mathematical Foundations of Computer Science from 1977 to 1981, and served on the Council of EATCS (European Association for Theoretical Computer Science) from 1977 to 1985. He was editor of three monograph series, in particular being editor-in-chief of the series Progress in Theoretical Computer Science. He served as a member and as the chair of the program committees of numerous professional conferences including STOC (Annual ACM Symposium on Theory of Computing), FOCS (Annual IEEE Symposium on Foundations of Computer Science), ICALP (International Colloquium on Automata, Languages and Programming sponsored by the European Association of Theoretical Computer Science) and MFCS (International Symposium on Mathematical Foundations of Computer Science).

Book suffered from multiple sclerosis and his death at the age of sixty was a result of complications arising from that disease. He was survived by his wife Celia Wrathall. The book [1] is Festschrift for Book resulting from a colloquium at the University of Minnesota at Minneapolis on 12 April 1997. His death occurred about six weeks after this colloquium. Nivat ends his appreciation in [8] with these words:-

... it is certainly difficult to forget Ron's smile, Ron's gentleness from which he never departed whoever he was talking to and which hid an iron will to understand and to grow, theorem after theorem, nice scientific crops.

**Article by:** *J J O'Connor* and *E F Robertson*

**November 2004**

[http://www-history.mcs.st-andrews.ac.uk/Biographies/Book.html]