POPL 2024
Sun 14 - Sat 20 January 2024 London, United Kingdom

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 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
5m
Day opening
Opening
VMCAI

09:05
60m
Keynote
Two Projects on Human Interaction with AI
VMCAI
David Harel Weizmann Institute of Science, Israel
10:05
20m
Talk
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