The Work of Anil Nerode: A Retrospective
Jeffrey B. Remmel, John Newsome Crossley · Birkhäuser Boston eBooks · 1993
Anil Nerode’s work divides into a number of periods though, inevitably, there are overlaps and cross-currents. In this survey we indicate what we consider the highlights so far in mathematics and computer science. (We have not included his work in environmental science policy for the United States Environmental Protection Agency, except insofar as it is listed in the bibliography at the end (Loehr, Goldstein, Nerode & Risser [1992]).) We distinguish six periods or areas: 1. His thesis and early work in automata theory and recursion theory, 2. Isols, 3. Undecidability, 4. Recursive algebra, 5. Polynomial-time structures and 6. Computer science. From the authors’ personal experience, we know that much of Nerode’s effort has gone into developing foundations for various subjects. This, of course, means that a lot of his work has involved not only proving theorems but searching for the appropriate basic definitions which allow an area to be developed. Even though our space is limited, we hope to give some sense of this foundational work in this survey. Finally we should note that Nerode has made contributions to logic in general by his influence on other researchers in the field. This not only includes the 34 Ph.D. students that he has supervised to date, but also many researchers in logic who have benefited from his suggestions for areas of research to pursue, or approaches to a problem, as well as his enthusiastic encouragement of their efforts.