Speaker: Agnes Kurucz, Kings College London
UCL Contact: Robin Hirsch (Visitors from outside UCL please email in advance).
Date/Time: 26 Jun 12, 16:00 - 17:00
Venue: Roberts 508
KxK, the bimodal logic of all two-dimensional product frames, is known to be decidable. However, only nonelementary decision algorithms for KxK-satisfiability are known, and so far the best lower bound has been NEXPTIME (by Marx and Mikulas 2001). Recently, Goller, Jung, and Lohrey (LICS 2012) showed that KxK-satisfiability cannot be done in elementary time. Kikot and Kurucz 2012 showed that `KxK plus diagonal constant' is even worse, its satisfiability problem is undecidable. The talk is about the proofs of these two recent results.