IMDEA Software

IMDEA initiative

Home > Events > Software Seminar Series > 2019 > Undecidability and Context-Free Languages

Elena Gutiérrez Viedma

Monday, March 25, 2019

10:45am Lecture hall 1, level B

Elena Gutiérrez Viedma, PhD Student, IMDEA Software Institute

Undecidability and Context-Free Languages

Abstract:

Starting from one of the most celebrated undecidable problem in CS, the Halting Problem, and using reductions as a bridge to show that one problem is at least as difficult to solve as other hard problem, I will gradually achieve the goal of this presentation: proving the undecidability of a collection of problems on the theory of context-free languages.