Variant Narrowing and Equational Unification

Escobar, Santiago; Meseguer, José; Sasse, Ralf

Permalink

https://hdl.handle.net/2142/11404 Copy

Description

Title

Variant Narrowing and Equational Unification

Author(s)

• Escobar, Santiago
• Meseguer, José
• Sasse, Ralf

Issue Date

2007-10

Keyword(s)

computer science

Abstract

Narrowing is a well-known complete procedure for equational E-unification when E can be decomposed as a union E = \Delta \uplus B with B a set of axioms for which a finitary unification algorithm exists, and \Delta a set of confluent, terminating, and B-coherent rewrite rules. However, when B \not= \emptyset, efficient narrowing strategies such as basic narrowing easily fail to be complete and cannot be used. This poses two challenges to narrowing-based equational unification: (i) finding efficient narrowing strategies that are complete modulo B under mild assumptions on B, and (ii) finding sufficient conditions under which such narrowing strategies yield finitary E-unification algorithms. Inspired by Comon and Delaune's notion of E-variant for a term, we propose a new narrowing strategy called variant narrowing that has a search space potentially much smaller than full narrowing, is complete, and yields a finitary E-unification algorithm when E has the finite variant property. We furthermore identify a class of equational theories for which the finite bound ensuring the finite variant property can be effectively computed by a generic algorithm. We also discuss applications to the formal analysis of cryptographic protocols modulo the algebraic properties of the underlying cryptographic functions.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11404

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections