Ronald V. Book
# Ronald V. Book

Ronald „Ron“ Vernon Book (* 5. März 1937; † 28. Mai 1997 in Santa Barbara, Kalifornien) war ein US-amerikanischer Informatiker.

## Leben

Ronald Vernon Book ist in einer Landwirtschaft betreibenden Familie aufgewachsen. Er besuchte das Grinnell College, eine höhere Privatschule in Grinnel, Iowa und erhielt seinen B.A. 1958 als Abschluss. An der Wesleyan University, einer Privatuniversität in Middletown, Connecticut studierte er Mathematik und erhielt 1960 einen M.A. und 1964 einen zweiten M.A. Im Anschluss daran begann er mit seinen ersten Forschungen an der Harvard University unter der Anleitung von Sheila A. Greibach. Er promovierte 1969 (Doktorarbeit: Grammars with Time Functions) zum Ph. D. Im Jahr 1970 publizierte er mit Greibach die Arbeit: Quasi-realtime languages (siehe auch Quasi-Realzeit-Sprachen, das ist die Komplexitätsklasse Q).

Book wurde in Harvard eingestellt und wechselte später nach Yale. Im Jahr 1971 lernte er den französischen Wissenschaftler Maurice Nivat auf einer Art Summer School für Formale Sprachen an der University of Western Ontario, in London, Ontario kennen. Nivat zeigte sich sehr beeindruckt von Books Art. Beide blieben freundschaftlich verbunden.

Im Jahr 1972 publizierte Ron Book zwei Arbeiten: In On languages accepted in polynomial time trennte er verschiedene Polynomialzeitklassen und in Topics in formal language theory stellte er aktiv bearbeitete und zentrale Themen der Formalen Sprachen dar.

Im Jahr 1977 wurde Ron Book am Institut für Mathematik an der University of California at Santa Barbara (UCSB) zum Professor berufen. Er begann ein weiteres Thema in seine Untersuchungen mitaufzunehmen: Wortersetzungssysteme (engl.: string-rewriting systems). In den Achtzigern entstanden so zahlreiche Arbeiten.

Ronald Book starb an Multipler Sklerose. Seine Frau Celia Wrathall ist bekannt geworden durch mehrere Arbeiten in der Theoretischen Informatik (siehe z. B. Polynomialzeithierarchie).

## Rezension

Robert McNaughton vertritt die Ansicht, dass Ron Book in dieser Zeit die Arbeiten über Wortersetzungssysteme schrieb, die in diesem Thema den stärksten wissenschaftlichen Impakt hatten. Im Jahr 1993 schrieb er gemeinsam mit Friedrich Otto das Buch String-rewriting systems. In diesem sind die wichtigsten Ergebnisse über Wortersetzungssysteme zusammengefasst.

Auf der anderen Seite gab er der Komplexitätstheorie verschiedene neue Impulse, so führte er beispielsweise die Begriffe dünne Menge und Tally-Sprache in die Komplexitätstheorie ein. Zahlreiche Wissenschaftler wandten diese Technologien auf das P-NP-Problem an. Diese Arbeiten vermitteln heute einen tiefen Einblick in die Schwierigkeit dieses Problems. Weiterhin untersuchte und verfeinerte er die Relativierungsbegriffe der Komplexitätstheorie.

Ding Zhu Du und Keri-I Ko berichten über ihn, dass er in den Achtzigern mit seinen Ideen bis hin zur Anwendung der Kolmogorow-Komplexität der Wissenschaftlergemeinde sehr wichtige Impulse gegeben hat.

Diese starke Wirkung ist wesentlich dadurch geprägt worden, dass er mit vielen Wissenschaftlern intensiv zusammengearbeitet hat. So hat er regelmäßig Gäste (meist Postdoc-Studenten) in Santa Barbara aufgenommen. Einige darunter waren Humboldt-Stipendiaten aus Deutschland und sind heute bekannte Wissenschaftler wie Friedrich Otto und Uwe Schöning.

Für seine Leistungen wurde er Anfang der 1990er-Jahre mit dem Preis der Alexander von Humboldt-Stiftung ausgezeichnet. Dieser Preis bestand darin, dass ihm für ein Jahr lang ein Forschungsaufenthalt in Deutschland finanziert wurde.

## Wissenschaftliches Engagement

Ron Book publizierte über 150 Artikel in internationalen wissenschaftlichen Zeitschriften.

* 1970–1971 war er Mitglied im Executive Committee of SIGACT (Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory)
* 1977–1981 war er Chairman des Institute of Electrical and Electronics Engineers Technological Committee on Mathematical Foundations of Computer Science from 1977 to 1981
* 1977–1985 war er Council im EATCS (European Association for Theoretical Computer Science).

Weiterhin war er Editor von drei verschiedenen Monographie-Serien über Informatik.

Regelmäßig war er in einer der folgenden Konferenzen als Chair oder als Programmkomitee-Mitglied vertreten:

* 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)

## Doktoranden

Bei Ron Book haben promoviert:

* 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
