Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Proof-Producing Congruence Closure
verfasst von : Robert Nieuwenhuis, Albert Oliveras
Erschienen in: Term Rewriting and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Many applications of congruence closure nowadays require the ability of recovering, among the thousands of input equations, the small subset that caused the equivalence of a given pair of terms. For this purpose, here we introduce an incremental congruence closure algorithm that has an additional
$\mathit{Explain}$
operation.
First, two variations of union-find data structures with
$\mathit{Explain}$
are introduced. Then, these are applied inside a congruence closure algorithm with
$\mathit{Explain}$
, where a
k
-step proof can be recovered in almost optimal time (quasi-linear in
k
), without increasing the overall
O
(
n
log
n
) runtime of the fastest known congruence closure algorithms.
This non-trivial (ground) equational reasoning result has been quite intensively sought after (see, e.g., [SD99,dMRS04,KS04]), and moreover has important applications to verification.