Walter Savitch

John Walter Savitch ( born February 21, 1943) is an emeritus professor of computer science at the University of California, San Diego.

Savitch acquired in 1969 from the University of California, Berkeley Ph.D. degree in mathematics. He is especially known for it has the complexity class NL defines the non-deterministic logarithmic problems, and in particular also for the set of Savitch, which describes the relationship of the complexity classes DSPACE and NSPACE. The complexity class NL was the first formally defined NLOGSPACE complete language. This fundamental insight has led to more extensive research of the complete problems in the field of complexity theory. He has also contributed to the theories of non-deterministic and parallel computation models important work.

His research areas include complexity theory, formal languages ​​, and processing natural languages ​​/ computable languages. In addition to his work in theoretical computer science, Savitch some reference books for learning C / C , Java, Ada and other languages ​​has also written.