Order-sorted Equational Unification Revisited

Joe Hendrix, José Meseguer

Electronic Notes in Theoretical Computer Science · 2012 · 19 citations · 7 references

DOIFull text

Open access

Concepts

Abstract

This paper presents a rule-based algorithm for performing order-sorted E-unification using an unsorted E-unification decision procedure under assumptions about E that are commonly satisfied in practice. We have implemented this algorithm in Maude for use with the Maude-NRL protocol analyzer and have used CiME for unsorted E-unification for E any set of AC and ACU axioms. In many examples of interest, using order-sorted unification over unsorted unification is able to reduce the total number of unifiers considered, and dramatically improve the performance of the Maude-NRL tool.

References

7