Ronald V. Book

Ronald "Ron" Vernon Book (born March 5, 1937 - May 28, 1997 in Santa Barbara , California ) was an American computer scientist .

Life

Ronald Vernon Book grew up in a farming family. He attended Grinnell College, a higher private school in Grinnel , Iowa, and received his BA in 1958. At Wesleyan University , a private university in Middletown , Connecticut, he studied mathematics and received an MA in 1960 and a second MA in 1964. He then began his first research at Harvard University under the supervision of Sheila A. Greibach . He received his PhD in 1969 (doctoral thesis: Grammars with Time Functions ) . In 1970 he published the work with Greibach: Quasi-realtime languages (see also Quasi-Realtime Languages , which is the complexity class Q).

Book was hired at Harvard and later moved to Yale . In 1971 he met the French scientist Maurice Nivat at a kind of summer school for formal languages ​​at the University of Western Ontario in London , Ontario . Nivat was very impressed with Books Art. Both remained on friendly terms.

In 1972 Ron Book published two works: In On languages ​​accepted in polynomial time he separated different polynomial time classes and in Topics in formal language theory he presented actively worked on and central topics of formal languages.

In 1977, Ron Book was appointed professor at the Department of Mathematics at the University of California at Santa Barbara (UCSB). He began to include another topic in his research: string-rewriting systems. Numerous works were created in the eighties.

Ronald Book died of multiple sclerosis . His wife, Celia Wrathall, is best known for her work in theoretical computer science (see e.g. polynomial time hierarchy ).

review

Robert McNaughton believes that it was during this time that Ron Book wrote the work on word replacement systems that had the greatest scientific impact on this topic. In 1993 he wrote the book String-rewriting systems together with Friedrich Otto . This summarizes the most important results about word replacement systems.

On the other hand, he gave the complexity theory various new impulses, for example he introduced the terms thin set and tally language into complexity theory. Numerous scientists have applied these technologies to the P-NP problem . Today this work gives a deep insight into the difficulty of this problem. Furthermore, he examined and refined the relativization concepts of complexity theory.

Ding Zhu Du and Keri-I Ko report that he gave the scientific community very important impulses in the eighties with his ideas up to and including the application of Kolmogorow's complexity .

This strong effect was largely shaped by the fact that he worked intensively with many scientists. He has regularly hosted guests (mostly postdoc students) in Santa Barbara. Some of them were Humboldt fellows from Germany and are now well-known scientists such as Friedrich Otto and Uwe Schöning .

In the early 1990s he was awarded the Alexander von Humboldt Foundation Prize for his achievements . This award consisted of the fact that he was financed a research stay in Germany for one year.

Scientific commitment

Ron Book published over 150 articles in international scientific journals.

• 1970–1971 he was a member of the Executive Committee of SIGACT ( Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory)
• 1977–1981 he was Chairman of the Institute of Electrical and Electronics Engineers Technological Committee on Mathematical Foundations of Computer Science from 1977 to 1981
• 1977–1985 he was a council in EATCS ( European Association for Theoretical Computer Science ).

He was also the editor of three different series of monographs on computer science.

He was regularly represented in one of the following conferences as chair or as a program committee member:

• 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)
• MFCS (International Symposium on Mathematical Foundations of Computer Science)

PhD students

PhDs from Ron Book:

• Brenda Baker , Harvard University , 1973
• Ding Zhu Du , University of California, Santa Barbara , 1985
• Colm O'Dunlaing , University of California, Santa Barbara, 1981
• Luquan Pan , University of California, Santa Barbara, 1986
• David Russo , University of California, Santa Barbara, 1985

literature

• A summary of Ronald V. Book's scientific research. In: Advances in algorithms, languages, and complexity. Dordrecht, 1997, pp. Xv-xvii.
• Ding Zhu Du, Keri-I Ko: In memoriam Ronald V. Book. In: Theoretical Computer Science. 1, 207, 1998, pp. 1-3.
• In memoriam: Ronald V. Book, Bull. In: European Association of Theoretical Computer Science (EATCS). 63, 1997, p. 292.
• List of Ronald V. Book's publications. In memoriam of Ronald V Book. In theory. Comput. Sci .. 1, 207, 1998, pp. 5-11.
• List of Ronald V. Book's publications. In Advances in algorithms, languages, and complexity. Dordrecht, 1997, pp. Xxiii-xxxiv.
• Robert McNaughton: Contributions of Ronald V Book to the theory of string-rewriting systems. In memoriam of Ronald V Book. In: Theoret. Comput. Sci. 1, 207, 1998, pp. 13-23.
• Maurice Nivat: Foreword in memoriam Ronald V Book. In memoriam of Ronald V Book. In: Theoret. Comput. Sci. 1, 207, 1998, pp. Xiii-xiv.

Web links

• Literature by and about Ronald V. Book in the catalog of the German National Library
• John J. O'Connor, Edmund F. Robertson :  Ronald V. Book. In: MacTutor History of Mathematics archive .
• Ronald V. Book in the Mathematics Genealogy Project (English)