Viðburðir eftir árum

ICE-TCS seminar: Antonis Achilleos

The Completeness Problem for Modal Logic

  • 5.2.2018, 12:10 - 13:00


Date and time: Monday, 5 February 2018 from 12:10 till 13:00
Place: Room M1.11 at Reykjavik University

Title: The Completeness Problem for Modal Logic

Speaker: Antonis Achilleos (Reykjavik University)

We introduce the completeness problem for Modal Logic and examine its complexity. For a definition of completeness for formulas, given a formula of a modal logic, the completeness problem asks whether the formula is complete for that logic. We discover that completeness and validity have the same complexity — with certain exceptions for which there are, in general, no complete formulas. To prove upper bounds, we present a non-deterministic polynomial-time procedure with an oracle from PSPACE that combines tableaux and a test for bisimulation, and determines whether a formula is complete.