Undecidability and Context-Free Languages

March 25, 2019

Elena Gutiérrez Viedma


Undecidability and Context-Free Languages

Time:   10:45am
Location:   Lecture hall 1, level B

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.