The 28th International Conference on Automated Deduction

The conference on Automated Deduction (CADE) is the major international forum at which research on all aspects of automated deduction is presented. The conference programme includes invited talks, paper presentations, workshops, tutorials, and system competitions. Furthermore, the Herbrand Award for Distinguished Contributions to Automated Deduction, the new Skolem Award(s) for influential historical CADE papers, and the Bill McCune PhD Award, are presented at the conference.

The 28th International Conference on Automated Deduction (CADE-28) will be virtual due to the COVID-19 pandemic. The virtual conference will take place from July 11 to 16, 2021 as originally planned.

Submissions to CADE-28 can be made in two categories: Regular papers (up to 15 pages in LNCS style, excluding references) and short papers (up to 10 pages in LNCS style, excluding references). More information about submission can be found in the joint Call for Papers and Workshops/Tutorials/Competitions.

The authors of a selection of the best CADE-28 papers will be invited to submit an extended version of their paper after the conference, to be published in a special issue of the Journal of Automated Reasoning.

CADE-28 is organized in cooperation with ACM SIGLOG.

Accepted papers will be published in Lecture Notes in Artificial Intelligence (Springer) with Open Access.

Gates Hillman Center at CMU

All dates are Anywhere on Earth.

Events

Workshops+Tutorials: July 11 and 16, 2021
Conference: July 12 - 15, 2021

Papers

Papers must be submitted to the CADE-28 track via EasyChair.
All papers must include the ORCID ids of authors (at least the corresponding author).

Abstract deadline: February 15, 2021
Submission deadline: February 22, 2021 (AoE, no extensions)
Rebuttal phase: March 29 to March 31, 2021
Notification: April 9, 2021
Final version: April 30, 2021

Liron Cohen, Ben-Gurion University

Title: Non-well-founded deduction for induction and coinduction

Induction and coinduction are both used extensively within mathematics and computer science. Algebraic formulations of these principles make the duality between them apparent, but do not account well for the way they are commonly used in deduction. Generally, the formalization of these reasoning methods employs inference rules that express a general explicit (co)induction scheme. Non-well-founded proof theory provides an alternative, more robust approach for formalizing implicit (co)inductive reasoning. This approach has been extremely successful in recent years in supporting implicit inductive reasoning, but is not as well-developed in the context of coinductive reasoning. This talk reviews the general method of non-well-founded proofs, and puts forward a concrete natural framework for (co)inductive reasoning, based on (co)closure operators, that offers a concise framework in which inductive and coinductive reasoning are captured as we intuitively understand and use them. Through this framework we demonstrate the enormous potential of non-well-founded deduction, both in the foundational theoretical exploration of (co)inductive reasoning and in the provision of proof support for (co)inductive reasoning within (semi-)automated proof tools.

Bio: Liron Cohen is senior lecturer (assistant professor) in the Department of Computer Science at Ben-Gurion University in Israel. Previously, Liron was a Fulbright postdoctoral researcher at Cornell University working with Robert Constable. She obtained her Ph.D. in 2016 from Tel Aviv University advised by Arnon Avron. Liron's research is motivated by the desire to understand the deep connection between proofs and computation. Her research interests include computer-aided deduction and verification, type systems, logics, programming languages and computational mathematics.

Mooly Sagiv, Tel Aviv University

Title: Taming Verification Conditions for Diagnosable Verification

One of the most difficult aspects in formally verifying infinite state systems is reasoning about quantifiers and specifically quantifier altenerations. Indeed alternation cycles lead to divergence and instability of modern SMT solvers. We describe abstractions for preventing cycles and evaluate their effectiveness by verifying tricky distributed protocols. The first abstraction is modularity: break the system into modules and separately verify each module by hiding some dependencies to avoid cycles. The second approach introduces a novel interactive approach to quantifier reasoning using an SMT solver. We automatically abstract the verification condition in a way that eliminates function cycles. The user refines this abstraction in response to spurious counterexamples by proposing ground terms to instantiate quantifiers. In applying this approach to the verification of Byzantine and non-Byzantine fault tolerance protocols, we found that a few manual instantiations were needed. Moreover, the counterexamples provided valuable guidance for the user, in contrast to the timeouts produced by the traditional approach.

Bio: Mooly Sagiv is a professor in the School of Computer Sciences at Tel-Aviv University and a CEO and co-founder of Certora. He is a leading researcher in the area of large scale (inter-procedural) program analysis, and one of the key contributors to shape analysis. His fields of interests include programming languages, compilers, abstract interpretation, profiling, pointer analysis, shape analysis, inter-procedural dataflow analysis, program slicing, and language-based programming environments.

Guido Governatori, CSIRO

Title: Computational Law: Automated Reasoning in the Legal Domain

Bio: Guido Governatori leads the Software Systems Research Group and research activities on legal informatics at CSIRO's Data61. He received his PhD in Legal Informatics from the University of Bologna. His research has focused on automated reasoning techniques for non-classical logic, modal logic and non-monotonic reasoning (including labelled tableaux for modal logic, rule-based systems, and defeasible logic), and their applications in the legal domain, autonomous agents and business processes.

Markus Rabe, Google

Title: What are the Limits of Neural Networks for Automated Reasoning?

Theorem proving with neural networks has made large strides. From using learned heuristics instead of handwritten heuristics, to learning to retrieve premises, to directly predicting proofs using language models; neural networks appear to be surprisingly capable at working with abstract mathematics. This talk gives an overview of recent advances in the field and the paradigms behind them, as well as an outline of the plans of the N2Formal team at Google Research.

Bio: Markus N. Rabe is a software engineer and researcher at Google. He explores the foundations of automated reasoning, including the use of deep learning, and is a member of the N2Formal team, which has the goal to automatically formalize mathematics. Markus has a Ph.D. from Saarland University and visited UC Berkeley as a postdoc.

Workshops

July 11

Theorem Proving Components for Educational Software (ThEdu'21)

Workshop on Proof eXchange for Theorem Proving (PxTP)

Parallel and Distributed Automated Reasoning

July 16

17th International Workshop on Termination (WST 2021)

International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice (LFMTP)

3rd International Workshop on Automated Reasoning: Challenges, Applications, Directions, Exemplary Achievements (ARCADE)

Tutorials

July 11

Program Validation and Verification in PVS

Paolo Masci (NIA), Mariano Moscato (NIA), César Munoz (NASA), Aaron Dutle (NASA), and Tanner Slagel (NASA)

This tutorial provides a gentle introduction to PVS 7.1, recently released, through the most recent versions of NASALib and VSCode-PVS. The tutorial is structured as a hands-on activity with lectures and exercises. Attendees are encouraged to bring their own laptops (Linux or Mac OSX).

Practice of First-Order Reasoning

Stephan Schulz (DHBW), Adam Pease (Articulate Software), and Geoff Sutcliffe (University of Miami)

The tutorial will use PyRes, a simple but complete automatic theorem prover for first-order logic. PyRes has been particularly designed with a pedagogical purpose in mind. It is written in clear, extensively documented Python code. The tutorial will acquaint the participants with the architecture and implementation of a saturating first-order reasoning system. The morning sessions will comprise presentations on the most important aspects of resolution-based theorem proving and their realization in PyRes. Afternoon sessions will be supervised programming exercises by the participants, with the goal of building improved variants of the prover.
The tutorial will conclude with a small CASC-like competition where the different teams can compare the effects of their improvements. Systems that perform well will be eligible for late entry into the demonstration division of CASC.

July 16

Learning to Prove: Machine Learning for Better SAT and QSAT Solvers

Sean Holden (Univeristy of Cambridge)

Satisfiability (SAT) and quantified satisfiability (QSAT) solvers are a fundamental concern for the field of Automated Deduction. While machine learning (ML) is currently an immensely fashionable area, it might not be apparent to many that ML researchers have been applying their work to SAT and QSAT solvers since the late 1980s; and, in fact, numerous aspects of various state-of-the-art solvers employ ele- ments of ML. More recently SAT and QSAT solvers have become an application of interest within the area of deep ML, and the application of these techniques turns out to raise new issues. This tutorial aims to provide an overall introduction to how ML has been applied to date to SAT and QSAT solving, with the aim of providing interested researchers with sufficient background to help move the field forward.

Proof-Theoretical Analysis of Non-Fregean Logic

Szymon Chlebowski, Marta Gawek, Dorota Leszczyńska-Jasion, and Agata Tomczyk (Adam Mickiewicz University)

The tutorial focuses on proof-theory for non-Fregean logics. We will pay special attention to structural proof theory taking into considerations sequent systems and natural deduction systems. The issues of cut-elimination and normalization will be discussed. However, we will also present tableau systems (Rasiowa-Sikorski formalization, dual tableaux, synthetic tableaux) for non-Fregean logics. Finally, we will sketch the ideas how to use the variety of proof systems in facilitating automated proof search in propositional logics with identity.

Competitions

The CADE ATP System Competition (CASC)

Termination and Complexity Competition (termCOMP)

Alexander Bentkamp, Jasmin Blanchette, Sophie Tourret and Petar Vukmirović. Superposition for Full Higher-Order Logic

Petar Vukmirović, Alexander Bentkamp, Jasmin Blanchette, Simon Cruanes, Visa Nummelin and Sophie Tourret. Making Higher-Order Superposition Work

Gabriel Ebner, Jasmin Blanchette and Sophie Tourret. A Unifying Splitting Framework

Visa Nummelin, Alexander Bentkamp, Sophie Tourret and Petar Vukmirović. Superposition with First-Class Booleans and Inprocessing Clausification

Randal Bryant and Marijn Heule. Dual Proof Generation for Quantified Boolean Formulas with a BDD-Based Solver

Hans-Jörg Schurr, Mathias Fleury and Martin Desharnais. Reliable Reconstruction of Fine-Grained Proofs in a Proof Assistant

Christian Alrabbaa, Franz Baader, Stefan Borgwardt, Patrick Koopmann and Alisa Kovtunova. Finding Good Proofs for Description Logic Entailments Using Recursive Quality Measures

Camillo Fiorentini. Efficient SAT-based proof search in Intuitionistic Propositional Logic

Alessandro Cimatti, Alberto Griggio and Gianluca Redondi. Universal Invariant Checking of Parametric Systems with Quantifier-Free SMT Reasoning

Fajar Haifani, Sophie Tourret and Christoph Weidenbach. Generalized Completeness for SOS Resolution and its Application to a New Notion of Relevance

Mnacho Echenim, Radu Iosif and Nicolas Peltier. Unifying Decidable Entailments in Separation Logic with Inductive Definitions

Nicholas Smallbone. Twee: an equational theorem prover (System Description)

Kaustuv Chaudhuri. Subformula Linking for Intuitionistic Logic and Type Theory

Tobias Nipkow and Simon Roßkopf. Isabelle's Metalogic: Formalization and Proof Checker

Ying Sheng, Yoni Zohar, Christophe Ringeissen, Andrew Reynolds, Clark Barrett and Cesare Tinelli. Politeness and Stable Infiniteness: Stronger Together

Emery Neufeld, Ezio Bartocci, Agata Ciabattoni and Guido Governatori. A Normative Supervisor for Reinforcement Learning Agents (System Description)

Leonardo de Moura and Sebastian Ullrich. The Lean 4 Theorem Prover and Programming Language (System Description)

Adrian De Lon, Peter Koepke, Anton Lorenzen, Adrian Marti, Marcel Schütz and Makarius Wenzel. The Isabelle/Naproche Natural Language Proof Assistant (System Description)

Fabio Papacchini, Cláudia Nalon, Ullrich Hustadt and Clare Dixon. Efficient Local Reductions to Basic Modal Logic

Lee Barnett and Armin Biere. Non-Clausal Redundancy Properties

Ryan Krueger, Jesse Michael Han and Daniel Selsam. Automatically Building Diagrams for Olympiad Geometry Problems (System Description)

Jacob Errington, Junyoung Jang and Brigitte Pientka. Harpoon: Mechanizing Metatheory Interactively (System Description)

Franz Brauße, Konstantin Korovin, Margarita Korovina and Norbert Th. Müller. The ksmt calculus is a delta-complete decision procedure for non-linear constraints

Dohan Kim and Christopher Lynch. Equational Theorem Proving Modulo

Franz Baader, Patrick Koopmann, Francesco Kriegel and Adrian Nuradiansyah. Computing Optimal Repairs of Quantified ABoxes w.r.t. Static EL TBoxes

Vivek Nigam, Giselle Reis, Samar Rahmouni and Harald Ruess. Proof Search and Certificates for Evidential Transactions

Martin Suda. New Techniques that Improve ENIGMA-style Clause Selection Guidance

Petra Hozzová, Laura Kovács and Andrei Voronkov. Integer Induction in Saturation

Emre Yolcu, Scott Aaronson and Marijn Heule. An Automated Approach to the Collatz Conjecture

Joanna Golinska-Pilarek, Michal Zawidzki and Taneli Huuskonen. Tableau-based decision procedure for non-Fregean logic of sentential identity

Tanel Tammet, Dirk Draheim and Priit Järv. Confidences for Commonsense Reasoning

Akihisa Yamada. Multi-Dimensional Interpretation Methods for Termination of Term Rewriting

Peter Baumgartner. The Fusemate Logic Programming System (System Description)

Runqing Xu, Liming Li and Bohua Zhan. Verified interactive computation of definite integrals

Christoph Wernhard and Wolfgang Bibel. Learning from Łukasiewicz and Meredith: Investigations into Proof Structures

Filip Bártek and Martin Suda. Neural Precedence Recommender

PC Chairs

André Platzer, Carnegie Mellon University
Geoff Sutcliffe, University of Miami

Local Organizers

Marijn Heule, Carnegie Mellon University
André Platzer, Carnegie Mellon University
Iliano Cervesato, Carnegie Mellon University

Workshop and Tutorial Chair

Alexander Steen, University of Luxembourg

Publicity Chair

Sophie Tourret, Max Planck Institute

Program Committee

Peter Baumgartner, CSIRO
Bernhard Beckert, Karlsruhe Institute of Technology
Christoph Benzmüller, Freie Universität Berlin
Armin Biere, Johannes Kepler University Linz
Nikolaj Bjorner, Microsoft
Jasmin Blanchette, Vrije Universiteit Amsterdam
Maria Paola Bonacina, Università degli Studi di Verona
Agata Ciabattoni, Vienna University of Technology
Koen Claessen, Chalmers University of Technology
Hans de Nivelle, School of Engineering and Digital Sciences Nazarbayev University
Stéphane Demri, LSV CNRS ENS Paris-Saclay
Huimin Dong, Zhejiang University
Gilles Dowek, INRIA and ENS Paris-Saclay
Mnacho Echenim, University of Grenoble
Pascal Fontaine, Université de Liège Belgium
Nathan Fulton, IBM
Silvio Ghilardi, Dipartimento di Matematica Università degli Studi di Milano
Jürgen Giesl, RWTH Aachen University
Rajeev Gore, The Australian National University
Nao Hirokawa, JAIST
Moa Johansson, Chalmers University of Technology
Dejan Jovanović, SRI International
Cezary Kaliszyk, University of Innsbruck
Laura Kovacs, Vienna University of Technology
Tomer Libal, American University of Paris
Assia Mahboubi, INRIA
Cláudia Nalon, University of Brasília
Vivek Nigam, fortiss GmbH
Tobias Nipkow, Technical University of Munich
Frank Pfenning, Carnegie Mellon University
Giles Reger, The University of Manchester
Andrew Reynolds, University of Iowa
Philipp Ruemmer, Uppsala University
Katsuhiko Sano, Faculty of Humanities and Human Sciences Hokkaido University
Renate A. Schmidt, The University of Manchester
Stephan Schulz, DHBW Stuttgart
Viorica Sofronie-Stokkermans, University Koblenz-Landau
Martin Suda, Czech Technical University in Prague
Tanel Tammet, Tallinn University of Technology
Sophie Tourret, Max Planck Institute for Informatics
Christian Urban, King's College London
Uwe Waldmann, MPI for Informatics
Yoni Zohar, Stanford University

CADE implements the ACM policy against harassment.