MacTutor
Professor Ronald V. Book passed away on May 28, 1997, from complications of multiple sclerosis. He is survived by his wife, Celia Wrathall Book of Santa Barbara, California; and his brother, Robert Book of Wilton, Connecticut. He was 60 years old.
Ron Book had been a member of the UCSB Mathematics faculty since 1976. He was a renowned leader in theoretical computer science, with numerous publications in the fields of structural complexity theory, rewriting systems, and formal languages. He was an outstanding teacher of graduate students, and the UCSB Mathematics Department is especially proud of the fine researchers who have obtained their Ph.D.'s under his direction. He was equally outstanding as a teacher of undergraduates, and for many years was regarded as one of the best teachers in the department by undergraduate students.
Professor Book initiated his academic career in 1958, graduating from Grinnell College with a Bachelor of arts degree. He obtained a Master of Arts in Teaching degree in 1960 and a Master of Arts degree in 1964 both from Wesleyan University, and a Doctor of Philosophy degree from Harvard University in 1969, under the guidance of Professor Sheila A. Greibach. He taught at Harvard University and then at Yale University. He joined the UCSB faculty as a full professor in 1976.
Book made substantial contribution to the computer science community through his selfless services. He held editorial positions with 12 professional journals, and was editor-in-chief of three monograph series. Book served as a member and the chair of the program committees of a number of professional conferences.
Ron Book was a leading contributor to formal language theory, structural complexity theory, and the theory of string rewriting systems throughout his career. His research in discrete mathematics and theoretical computer science is reflected in more than 150 scientific publications. These works have made strong impact in the development of several areas of theoretical computer science, including languages, algorithms, and computational complexity.
During the 1980s he studied Semi-Thue systems, also known as string-rewriting systems, extensively. Such systems are at the very heart of formal language theory. They yield a connection between formal language theory and combinatorial semigroup theory. It was Book who first stressed algorithmic questions and their inherent complexity for these systems. He presented an algorithm in the form of a two-pushdown automaton that solves the word problem for a finite, length-reducing, and confluent semi-Thue system in linear time. This algorithm establishes a close correspondence between the lengths of left-most reduction sequences and the complexity of the word problem, and this correspondence is not restricted to length-reducing systems. In a series of papers Book and his collaborators also addressed many other important algorithmic problems for semi-Thue systems.
Another important theme of Book's work on languages was the correspondence between the combinatorial properties of a semi-Thue system and the language-theoretical properties of the Thue congruence generated. Book addressed the important question of characterizing those semi-Thue systems for which there exists an equivalent semi-Thue system that is convergent. This question continues to receive a lot of attention, and many interesting results have been obtained.
One of the main contributions of Book in complexity theory was the study of restrictive relativization. This research was motivated by the relativization results such as those of Baker, Gill and Solovay and Book and his co-authors. Many central questions in complexity theory about the relation between two complexity classes, such as the P = ?NP question, are unrelativizable, in the sense that their answers could be both yes and no depending upon the oracles with respect to which the relativization is defined. A critical observation is that some of the seemingly natural relativizations actually provide unfair extra power to some types of machines than other types of machines. Therefore, in order to understand the real difference between the two types of machines, studies on restrictive relativization are necessary. Book initiated this research, and, in a series of papers, investigated intensively the effect of different types of restrictive relativization. His results revealed much insight into the computation of oracle machines, and strongly influenced the direction of research in relativization.
Research on sets with succinct descriptions studies the complexity of working with sets with short descriptions, including sparse sets and sets with low Kolmogorov complexity. Book was among the first to find the importance of tally sets and sparse sets. Besides the study of lowness of such sets and the characterization by low Kolmogorov complexity, he initiated the study of such sets by reducibility and equivalence to tally or sparse sets. These studies led to a long list of investigations in many different directions.
Another area in which Book made major contributions is the research on sets with high descriptive complexity. Book's investigations into this topic included the approaches by Kolmogorov randomness, complexity cores and random oracles. He gave precise characterizations of sets that are reducible to random sets in terms of sets that are reducible to almost all oracles, and thus providing yet another important connection between the notion of program-size randomness and the notion of probabilistically almost-all randomness.
Book's strong commitment to excellence in scholarship touched everyone who studied and worked with him. In 38 years of teaching, he produced 15 Ph.D. students. Ron also valued very much his work with postdoctoral researchers. Some of the finest young researchers in theoretical computer science spent periods as postdocs at UCSB; in all, he sponsored and supervised 14 postgraduate research fellows. His support, guidance, high standards, and infectious enthusiasm for research nurtured them at important junctures in their careers. Today, outstanding scientists who worked as postdocs with Ron Book may be found around the world.
Professor Book received a number of academic honors, including honorary faculty positions of Universidad Nacional San Antonio Abad of Peru and Beijing Computer Institute of China and the Senior U.S. Scientist Award of the Alexander von Humboldt Foundation. He frequently presented invited plenary lectures in international meetings.
A celebration of his 60th birthday was held in April, 1997, just a month before his death, at the University of Minnesota. On that occasion a volume of papers, edited by Ker-I Ko and Ding-Zhu Du, was published in his honor.
John Doner
Ding-Zhu Du
Ker-I Ko
Alan Selman
Klaus Wagner
Ron Book had been a member of the UCSB Mathematics faculty since 1976. He was a renowned leader in theoretical computer science, with numerous publications in the fields of structural complexity theory, rewriting systems, and formal languages. He was an outstanding teacher of graduate students, and the UCSB Mathematics Department is especially proud of the fine researchers who have obtained their Ph.D.'s under his direction. He was equally outstanding as a teacher of undergraduates, and for many years was regarded as one of the best teachers in the department by undergraduate students.
Professor Book initiated his academic career in 1958, graduating from Grinnell College with a Bachelor of arts degree. He obtained a Master of Arts in Teaching degree in 1960 and a Master of Arts degree in 1964 both from Wesleyan University, and a Doctor of Philosophy degree from Harvard University in 1969, under the guidance of Professor Sheila A. Greibach. He taught at Harvard University and then at Yale University. He joined the UCSB faculty as a full professor in 1976.
Book made substantial contribution to the computer science community through his selfless services. He held editorial positions with 12 professional journals, and was editor-in-chief of three monograph series. Book served as a member and the chair of the program committees of a number of professional conferences.
Ron Book was a leading contributor to formal language theory, structural complexity theory, and the theory of string rewriting systems throughout his career. His research in discrete mathematics and theoretical computer science is reflected in more than 150 scientific publications. These works have made strong impact in the development of several areas of theoretical computer science, including languages, algorithms, and computational complexity.
During the 1980s he studied Semi-Thue systems, also known as string-rewriting systems, extensively. Such systems are at the very heart of formal language theory. They yield a connection between formal language theory and combinatorial semigroup theory. It was Book who first stressed algorithmic questions and their inherent complexity for these systems. He presented an algorithm in the form of a two-pushdown automaton that solves the word problem for a finite, length-reducing, and confluent semi-Thue system in linear time. This algorithm establishes a close correspondence between the lengths of left-most reduction sequences and the complexity of the word problem, and this correspondence is not restricted to length-reducing systems. In a series of papers Book and his collaborators also addressed many other important algorithmic problems for semi-Thue systems.
Another important theme of Book's work on languages was the correspondence between the combinatorial properties of a semi-Thue system and the language-theoretical properties of the Thue congruence generated. Book addressed the important question of characterizing those semi-Thue systems for which there exists an equivalent semi-Thue system that is convergent. This question continues to receive a lot of attention, and many interesting results have been obtained.
One of the main contributions of Book in complexity theory was the study of restrictive relativization. This research was motivated by the relativization results such as those of Baker, Gill and Solovay and Book and his co-authors. Many central questions in complexity theory about the relation between two complexity classes, such as the P = ?NP question, are unrelativizable, in the sense that their answers could be both yes and no depending upon the oracles with respect to which the relativization is defined. A critical observation is that some of the seemingly natural relativizations actually provide unfair extra power to some types of machines than other types of machines. Therefore, in order to understand the real difference between the two types of machines, studies on restrictive relativization are necessary. Book initiated this research, and, in a series of papers, investigated intensively the effect of different types of restrictive relativization. His results revealed much insight into the computation of oracle machines, and strongly influenced the direction of research in relativization.
Research on sets with succinct descriptions studies the complexity of working with sets with short descriptions, including sparse sets and sets with low Kolmogorov complexity. Book was among the first to find the importance of tally sets and sparse sets. Besides the study of lowness of such sets and the characterization by low Kolmogorov complexity, he initiated the study of such sets by reducibility and equivalence to tally or sparse sets. These studies led to a long list of investigations in many different directions.
Another area in which Book made major contributions is the research on sets with high descriptive complexity. Book's investigations into this topic included the approaches by Kolmogorov randomness, complexity cores and random oracles. He gave precise characterizations of sets that are reducible to random sets in terms of sets that are reducible to almost all oracles, and thus providing yet another important connection between the notion of program-size randomness and the notion of probabilistically almost-all randomness.
Book's strong commitment to excellence in scholarship touched everyone who studied and worked with him. In 38 years of teaching, he produced 15 Ph.D. students. Ron also valued very much his work with postdoctoral researchers. Some of the finest young researchers in theoretical computer science spent periods as postdocs at UCSB; in all, he sponsored and supervised 14 postgraduate research fellows. His support, guidance, high standards, and infectious enthusiasm for research nurtured them at important junctures in their careers. Today, outstanding scientists who worked as postdocs with Ron Book may be found around the world.
Professor Book received a number of academic honors, including honorary faculty positions of Universidad Nacional San Antonio Abad of Peru and Beijing Computer Institute of China and the Senior U.S. Scientist Award of the Alexander von Humboldt Foundation. He frequently presented invited plenary lectures in international meetings.
A celebration of his 60th birthday was held in April, 1997, just a month before his death, at the University of Minnesota. On that occasion a volume of papers, edited by Ker-I Ko and Ding-Zhu Du, was published in his honor.
John Doner
Ding-Zhu Du
Ker-I Ko
Alan Selman
Klaus Wagner
This University of California obituary is available at THIS LINK