Gödel Prize - 2002

Géraud Sénizergues

The 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"
Theoretical Computer Science 251 (2001), 1-166

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.

e-max.it: your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.