Communication Dans Un Congrès Année : 2024

On the (In-)Completeness of Destructive Equality Resolution in the Superposition Calculus

Résumé

Bachmair's and Ganzinger's abstract redundancy concept for the Superposition Calculus justifies almost all operations that are used in superposition provers to delete or simplify clauses, and thus to keep the clause set manageable. Typical examples are tautology deletion, subsumption deletion, and demodulation, and with a more refined definition of redundancy joinability and connectedness can be covered as well. The notable exception is Destructive Equality Resolution, that is, the replacement of a clause $x \not\sim t$ with $x \notin \mathit{vars}(t)$ by $C\{x \rightarrow t\}$. This operation is implemented in state-of-the-art provers, and it is clearly useful in practice, but little is known about how it affects refutational completeness. We demonstrate on the one hand that the naive addition of Destructive Equality Resolution to the standard abstract redundancy concept renders the calculus refutationally incomplete. On the other hand, we present several restricted variants of the Superposition Calculus that are refutationally complete even with Destructive Equality Resolution.

Fichier principal
Vignette du fichier
paper.pdf (467.42 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
licence
Copyright (Tous droits réservés)

Dates et versions

hal-04907521 , version 1 (23-01-2025)

Licence

Copyright (Tous droits réservés)

Identifiants

Citer

Uwe Waldmann. On the (In-)Completeness of Destructive Equality Resolution in the Superposition Calculus. 12th International Joint Conference on Automated Reasoning (IJCAR 2024), Jul 2024, Nancy, France. pp.244-261, ⟨10.1007/978-3-031-63498-7\_15⟩. ⟨hal-04907521⟩
0 Consultations
0 Téléchargements

Altmetric

Partager

More