Fechar

Palestra 7/jul 14h, 511 RDC: "Cut-elimination and the decidability of reachability in alternating pushdown systems" – Prof. Gilles Dowek (INRIA)

Palestra: “Cut-elimination and the decidability of reachability in alternating pushdown systems”
Palestrante: Prof. Gilles Dowek (INRIA)
Data e horário: 7/jul 14h
Local: 511 RDC

Proof theory and automata theory both provide methods to prove
decidability results. We will show in this talk that, despite differences
in their presentation, some proof-theoretical and automata-theoretical
methods essentially are the same. More precisely, we will give a new proof
of the decidability of accessibility in alternating pushdown systems,
showing that it is a consequence of a cut-elimination theorem for a
natural-deduction like system.

(Gilles Dowek et Ying Jiang)