Department of Computer Science

PassivSystems Ltd wins Knowledge Transfer Business of the Year Award

Read this story >

Home
Prospective Students
- Virtual Open Day
- Undergraduate:
- BSc Computer Science
- MEng Computer Science
- MEng International
- MEng Mathematical Computation
- Specialist Postgraduate:
- MSc CSML
- MSc CGVI
- MSc FRM
- MSc FSE
- MSc HCIErg
- MSc ISec
- MSc ML
- MSc NCS
- MSc SSE
- MSc Web Sci BDA
- MRes Web Science
- MSc ICT Innovation
- Generalist Postgraduate:
- MSc Computer Science
- MSc Financial Computing
- Research:
- PhD Programme
- EngD Programme
- UK PhD Centre in Financial Computing
- UCL SECReT
Current Students
- Undergraduate Programmes
- First Year
- Second Year
- Third Year
- Fourth Year
- International Programme
- Affiliate Students
- Non-CS Students
- Specialist MSc Programmes
- MSc CSML
- MSc CGVI
- MSc FRM
- MSc FSE
- MSc HCI-E
- MSc ISec
- MSc ML
- MSc NCS
- MSc SSE
- Generalist MSc Programmes
- MSc CS
- MSc FC
- Research Degrees
- EngD VEIV
- MPhil/PhD
- PhD in FC
- Further Information
- Student Information
- Undergraduate Information
- Syllabus Information
Research
Alumni
Careers
Business and Collaboration
People
Getting Here
Job Vacancies

On the complexity of KxK, with and without the diagonal constant

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

Abstract

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.