Previous  (Chronologically)  Next  Main Index 
Previous  (Alphabetically)  Next  Biographies index 
Version for printing 
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 Quasirealtime languages and they described the contents of the paper as follows:
The quasirealtime languages are seen to be the languages accepted by nondeterministic multitape Turing machines in real time. The family of quasirealtime languages forms an abstract family of languages closed under intersection, linear erasing, and reversal. It is identical with the family of languages accepted by nondeterministic multitape Turing machines in linear time. Every quasirealtime language can be accepted in real time by a nondeterministic one stack, one pushdown store machine, and can be expressed as the lengthpreserving homomorphic image of the intersection of three contextfree 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 nondeterministic Turing machines in polynomial time, the corresponding family for deterministic Turing machines, the family of contextsensitive 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 Section 2, examples are given to explain the notion of finite specification of languages and the Chomsky hierarchy is defined. In Sections 3 through 5, several sets of questions are discussed with answers phrased in terms of the Chomsky hierarchy. Some of the results on contextfree languages are stated in Section 6, and extensions of contextfree languages are sketched in 7. In Section 8, some questions on contextsensitive grammars are discussed, and in Section 9, complexity classes of formal languages are studied. Section 10 contains a description of the metatheory and Section 11 highlights 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 in 1971 in 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 time 11, 8 and 4. 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 of 300 inhabitants where I bought an old farm house in 1973. Twentyfive 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 stringrewriting systems, and monoid presentations. For example in 1981 he published Thue congruences and the ChurchRosser 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 ChurchRosser case is tractable which shows that there is a polynomialtime algorithm for deciding whether a finite monadic ChurchRosser Thue system defines a group.
McNaughton writes in [7]:
During most of the 1980s Book was intensively interested in [stringrewriting 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 postdoctoral 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 postdocs 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 Stringrewriting systems (1993) on which he collaborated with Fred Otto.
However Book worked on other topics at the same time as he studied rewriting systems. DZ Du and KI 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 early 1980s 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 197071 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 editorinchief 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
List of References (8 books/articles)
 
Mathematicians born in the same country

Other Web sites  
JOC/EFR © November 2004 Copyright information 
School of Mathematics and Statistics University of St Andrews, Scotland  
The URL of this page is: http://wwwhistory.mcs.standrews.ac.uk/Biographies/Book.html 