Sound Over-Approximation of Equational Reasoning with Variable-Preserving Rules Parameterized by Derivation Depth
Authors: Mateus de Oliveira Oliveira
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result (Theorem 11) states that for each fixed set E of variable-preserving equations, the set of ground equations derivable from E in depth at most d is soundly over-approximable in fixed-parameter tractable time. More specifically, we devise an algorithm that takes as input a set E of variable-preserving equations and a target ground equation t t , and always halts with a YES or NO answer. |
| Researcher Affiliation | Academia | Department of Computer and Systems Sciences, Stockholm University, Sweden Department of Informatics, University of Bergen, Norway EMAIL |
| Pseudocode | No | The paper describes an algorithm and its properties (Theorem 11, Lemma 10), and outlines its steps conceptually in the proof of Theorem 11, but does not present a clearly structured pseudocode block or algorithm figure. |
| Open Source Code | No | The paper does not contain any statements about releasing source code, nor does it provide any links to a code repository or supplementary materials for code. |
| Open Datasets | No | The paper focuses on theoretical equational reasoning and term rewriting systems. It does not describe or utilize any experimental datasets. |
| Dataset Splits | No | The paper does not involve experimental evaluation using datasets, and therefore no dataset splits are mentioned. |
| Hardware Specification | No | The paper presents theoretical work on equational reasoning and does not describe any computational experiments that would require specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper presents theoretical work and does not describe any computational experiments requiring specific software implementations with version numbers. Therefore, no software dependencies are listed. |
| Experiment Setup | No | The paper is theoretical in nature, focusing on algorithms, lemmas, and proofs for equational reasoning. It does not describe any experiments, and therefore no experimental setup details, hyperparameters, or training configurations are provided. |