June 18, 2003

CSE celebrated Walt Savitch's 60th birthday as well as his 30+ years of service to UCSD at an event held at UCSD's Eucalyptus point on June 12, 2003. The event featured two distinguished speakers, Professor Stephen Cook (University of Toronto) and Professor Aravind Joshi (University of Pennsylvania). Professor Cook was Walt Savitch's PhD advisor at UC Berkeley. Professor Joshi is fellow of the ACM and National Academy of Engineering member, was the first recipient of the Association of Computational Linguistics Lifetime Achievement award and the 3rd recipient of the Rumelhart Prize in Cognitive Science ("the Nobel Prize of Cognitive Science") on the virtues of Tree-Adjoining Grammars in Natural Language Processing. A reception in honor of Professor Savitch concluded the program.

Walter Savitch joined the UCSD faculty in 1969, after receiving his Ph.D. in Mathematics from UC Berkeley that same year. He did his undergraduate work at the University of New Hampshire in Durham. Savitch served as director of the Interdisciplinary Ph.D. Program in Cognitive Science at UCSD for over ten years. He has served as a visiting researcher in the computer science departments of the University of Washington in Seattle, University of Cincinnati, and the University of Colorado in Boulder, and has been a visiting scholar at the Netherlands' Centrum voor Wiskunde en Informatica in Amsterdam. Professor Savitch is retiring at the end of the 2002-03 academic year. The department offers it deepest thanks to Walt for his years of service and wishes him the best of luck in his future endeavors.

Gary Cottrell, CSE Professor and colleague of Professor Savitch, offered the following testimonial:

"Walt started life in the area of theory of computation. As many of you are aware, one of his most famous results bears his name, "Savitch's theorem", which says that you can simulate a non-deterministic Turing machine that uses space S with a deterministic one that uses space S-squared. When I arrived at UCSD, Walt had become interested in computational modeling of Natural Language. This led to a result you are probably much less aware of, but it is one of my favorites. One of the proofs that natural languages are not Context Free is based on Swiss German, where a construct similar to the "respectively" construct in (John, Mary and Ted are a boy, a girl and a dog, respectively) actually requires the corresponding elements of the construct to be indexed syntactically. This is called reduplication (or cross-serial dependency) by linguists, and we have something like it in English with the "X or no X" construct (as in, "reduplication or no reduplication, I want a parse tree"). This corresponds to the famous context sensitive example, WW, i.e., strings like ABCABC, which cannot be handled by a pushdown automaton. Walt invented a new machine, which recognizes what I think is the smallest extension of context free languages that can handle the respectively construct called the reduplicative context free languages. The simple idea is to place a token on the stack, and then nondeterministically you can flip the stack down to the token, so now you can match the next string in the usual way. There is a version of the pumping lemma, etc. that goes through for this modified machine.

Besides these theoretical results, Walt was a terrific leader of the new AI group, and as many of us discovered, a great cook also! We will all miss him."

Links
Walt Savitch Research Profile
Walt Savitch Home Page
Stephen Cook Seminar Abstract - Relating Complexity Classes and Proposiitonal Proof Systems
Aravind Joshi Seminar Abstract - Starting with Complex Primitives Pays Off: Complicate Locally, Simplify Globally