2002 Gödel Prize
2002 Gödel Prize
Geraud Senizergues
Geraud Senizergues, for "L(A)=L(B)?
Decidability results from complete formal systems", Theoretical Computer
Science 251 (2001), pp.1-166. The author gives a complete solution to the
decidability of the equivalence problem for deterministic pushdown
automata: Given two languages L_1 and L_2 accepted by deterministic
pushdown automata decide whether L_1 = L_2. The problem was posed
by S. Ginsburg and S. Greibach in 1966 and various subcases were shown to
be decidable over the years. However, the full question remained elusive
until it was finally settled by the awardee. He showed the problem to be
decidable. The paper not only settles the equivalence problem for
deterministic context-free languages, but also develops an entire
machinery of new techniques which are likely to be useful in other
contexts. They have already found useful in semantics of programming
languages.
Created by
Wolfgang Bein,
July 27,2002
Last updated
Mon Jul 29 17:13:20 PDT 2002