Constrained Higher-Order Rewriting and Program Equivalence (CHORPE)

From February 2021 to January 2026 I will lead the NWO VIDI project Constrained Higher-Order Rewriting and Program Equivalence, grant number VI.Vidi.193.075. This page list the work performed as part of this project.

Project goals

The goal of CHORPE is to study program equivalence through translations to logically constrained term rewriting systems. Our particular focus is to translate higher-order features and use the knowledge of higher-order term rewriting analysis from the rewriting community.

Collaborations

We have started the TEA seminar, an online seminar uniting groups in Nijmegen, Amsterdam and Nagoya who all work on equivalence of and through term rewriting.

Publications

To date, the project has resulted in two publications in formal conference proceedings, and four informal papers documenting work in progress. Use the green download buttons to obtain the author copies.

Publications in formal conference proceedings

Cutting a Proof into Bite-Sized Chunks: Incrementally proving termination in higher-order term rewriting, by Cynthia Kop, proceedings for FSCD 2022

Analyzing Innermost Runtime Complexity Through Tuple Interpretations, by Liye Guo and Deivid Vale, proceedings for LSFA 2022

Publications in informal workshop proceedings

Higher-order LCTRSs and their termination, by Liye Guo and Cynthia Kop, proceedings for HOR 2023

Matrix invariants for program equivalence in LCTRSs, by Kasper Hagens and Cynthia Kop, proceedings for WPTE 2023

A transitive HORPO for curried systems by Liye Guo and Cynthia Kop, proceedings for WST 2022

Extending a Lemma Generation Approach for Rewriting Induction on Logically Constrained Term Rewriting Systems by Wouter Brozius, Kasper Hagens and Cynthia Kop, proceedings for WPTE 2022

Submitted to journals

• Complexity Analysis through Tuple Interpretations, by Liye Guo and Deivid Vale; submitted to Mathematical Structures in Computer Science (MSCS) for the special issue of LSFA 2022.

Project members

Cynthia Kop	Liye Guo	Kasper Hagens	Deivid Vale