POPL 2024 (series) / VMCAI 2024 (series) / VMCAI 2024 /
Interpolation and Quantifiers in Ortholattices
Mon 15 Jan 2024 10:05 - 10:25 at Marconi Room - Session 1: Openning, Keynote, SAT, SMT and Automated Reasoning Chair(s): Rayna Dimitrova
We study quantifiers and interpolation properties in emph{orthologic}, a non-distributive weakening of classical logic that is sound for formula validity with respect to classical logic and has a quadratic-time decision procedure. We present a sequent-based proof system for quantified orthologic, which we prove sound and complete for the class of all complete ortholattices. We show that orthologic does in general not admit quantifier elimination. Despite that, we show that interpolants always exists in orthologic. We give an algorithm to compute interpolants efficiently. We expect our result to be useful to quickly establish unreachability as a component of verification algorithms.
Mon 15 JanDisplayed time zone: London change
Mon 15 Jan
Displayed time zone: London change
09:00 - 10:30 | Session 1: Openning, Keynote, SAT, SMT and Automated ReasoningVMCAI at Marconi Room Chair(s): Rayna Dimitrova CISPA Helmholtz Center for Information Security | ||
09:00 5mDay opening | Opening VMCAI | ||
09:05 60mKeynote | Two Projects on Human Interaction with AI VMCAI David Harel Weizmann Institute of Science, Israel | ||
10:05 20mTalk | Interpolation and Quantifiers in Ortholattices VMCAI Sankalp Gambhir Ecole Polytechnique Federale de Lausanne (EPFL), Simon Guilloud École Polytechnique Fédérale de Lausanne, Viktor Kunčak EPFL, Switzerland |