Towards a Unified Proof Framework for Automated Fixpoint Reasoning using Matching Logic
Fri 20 Nov 2020 22:00 - 22:20 at SPLASH-I - F-2A Chair(s): Pranav Kant, Atsushi Igarashi
Automation of fixpoint reasoning has been extensively studied for various mathematical structures, logical formalisms, and computational domains, resulting in specialized fixpoint provers for heaps, for streams, for term algebras, for temporal properties, for program correctness, and for many other formal systems and inductive and coinductive properties. However, in spite of great theoretical and practical interest, there is no unified framework for automated fixpoint reasoning. Although several attempts have been made, there is no evidence that such a unified framework is possible, or practical. In this paper, we propose a candidate based on matching logic, a formalism recently shown to theoretically unify the above mentioned formal systems. Unfortunately, the (Knaster-Tarski) proof rule of matching logic, which enables inductive reasoning, is not syntax-driven. Worse, it can be applied at any step during a proof, making automation seem hopeless. Inspired by recent advances in automation of inductive proofs in separation logic, we propose an alternative proof system for matching logic, which is amenable for automation. We then discuss our implementation of it, which although not superior to specialized state-of-the-art automated provers for specific domains, we believe brings some evidence and hope that a unified framework for automated reasoning is not out of reach.
Fri 20 NovDisplayed time zone: Central Time (US & Canada) change
09:00 - 10:20 | F-2AOOPSLA at SPLASH-I +12h Chair(s): Aviral Goel Northeastern University, Reuben Rowe University College London | ||
09:00 20mTalk | A Sparse Iteration Space Transformation Framework for Sparse Tensor Algebra OOPSLA Ryan Senanayake Reservoir Labs, Changwan Hong Massachusetts Institute of Technology, Ziheng Wang Massachusetts Institute of Technology, Amalee Wilson Stanford University, Stephen Chou Massachusetts Institute of Technology, Shoaib Kamil Adobe Research, Saman Amarasinghe Massachusetts Institute of Technology, Fredrik Kjolstad Stanford University Link to publication DOI Pre-print Media Attached File Attached | ||
09:20 20mTalk | Resolution as Intersection Subtyping via Modus Ponens OOPSLA Koar Marntirosian KU Leuven, Tom Schrijvers KU Leuven, Bruno C. d. S. Oliveira University of Hong Kong, Georgios Karachalias Tweag Link to publication DOI Media Attached | ||
09:40 20mTalk | Guided Linking: Dynamic Linking without the Costs OOPSLA Sean Bartell University of Illinois at Urbana-Champaign, Will Dietz University of Illinois at Urbana-Champaign, Vikram S. Adve University of Illinois at Urbana-Champaign Link to publication DOI Media Attached | ||
10:00 20mTalk | Towards a Unified Proof Framework for Automated Fixpoint Reasoning using Matching Logic OOPSLA Xiaohong Chen University of Illinois at Urbana-Champaign, Minh-Thai Trinh Advanced Digital Sciences Center, Nishant Rodrigues University of Illinois at Urbana-Champaign, Lucas Peña University of Illinois at Urbana-Champaign, Grigore Roşu University of Illinois at Urbana-Champaign Link to publication DOI Media Attached |
21:00 - 22:20 | F-2AOOPSLA at SPLASH-I Chair(s): Pranav Kant University of Utah, Atsushi Igarashi Kyoto University, Japan | ||
21:00 20mTalk | A Sparse Iteration Space Transformation Framework for Sparse Tensor Algebra OOPSLA Ryan Senanayake Reservoir Labs, Changwan Hong Massachusetts Institute of Technology, Ziheng Wang Massachusetts Institute of Technology, Amalee Wilson Stanford University, Stephen Chou Massachusetts Institute of Technology, Shoaib Kamil Adobe Research, Saman Amarasinghe Massachusetts Institute of Technology, Fredrik Kjolstad Stanford University Link to publication DOI Pre-print Media Attached File Attached | ||
21:20 20mTalk | Resolution as Intersection Subtyping via Modus Ponens OOPSLA Koar Marntirosian KU Leuven, Tom Schrijvers KU Leuven, Bruno C. d. S. Oliveira University of Hong Kong, Georgios Karachalias Tweag Link to publication DOI Media Attached | ||
21:40 20mTalk | Guided Linking: Dynamic Linking without the Costs OOPSLA Sean Bartell University of Illinois at Urbana-Champaign, Will Dietz University of Illinois at Urbana-Champaign, Vikram S. Adve University of Illinois at Urbana-Champaign Link to publication DOI Media Attached | ||
22:00 20mTalk | Towards a Unified Proof Framework for Automated Fixpoint Reasoning using Matching Logic OOPSLA Xiaohong Chen University of Illinois at Urbana-Champaign, Minh-Thai Trinh Advanced Digital Sciences Center, Nishant Rodrigues University of Illinois at Urbana-Champaign, Lucas Peña University of Illinois at Urbana-Champaign, Grigore Roşu University of Illinois at Urbana-Champaign Link to publication DOI Media Attached |