Gödel Prize - 2002Géraud SénizerguesThe 2002 Gödel Prize for outstanding journal articles in the area of theoretical computer science will be awarded to the author of the paper: "L(A)=L(B)? Decidability Results from Complete Formal Systems" In his paper, the autor gives a positive solution to the decidability of the equivalence problem for deterministic pushdown automata: Given two languages L1 and L2 accepted by deterministic pushdown automata decide whether L1=L2. 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. |
