JFLP: Volume 1997, Article 7

The Journal of Functional and Logic Programming

Volume 1997

Article 7

Published by The MIT Press . Copyright 1997 Massachusetts Institute of Technology.

Your institution may already be a subscriber to JFLP. If not, please subscribe for legitimate access to all journal articles.

A Minimality Study for Set Unification

Puri Arenas-Sánchez and Agostino Dovier

4 December 1997

Abstract

A unification algorithm is said to be minimal for a unification problem if it generates exactly a (minimal) complete set of most-general unifiers, without instances, and without repetitions. The aim of this paper is to present a combinatorial minimality study for a significant collection of sample problems that can be used as benchmarks for testing any set-unification algorithm. Based on this combinatorial study, a new Set-Unification Algorithm (named SUA) is also described and proved to be minimal for all the analyzed problems. Furthermore, an existing naive set-unification algorithm has also been tested to show its bad behavior for most of the sample problems.

The following versions of the article are available:

• Preformatted versions of the article (compressed with gzip )
  • DVI (gzip'ped 72 kb)
  • PostScript (gzip'ped 287 kb)
  • PDF (gzip'ped 485 kb; uncompressed 692 kb)
• Source materials for custom formatting
  • LaTeX ( JFLP-A97-07.tex , gzip'ped 37 kb)
  • BIBTeX ( JFLP-A97-07.bib , gzip'ped 2 kb)
  • Parameter settings for custom formatting ( cjropts.tex , 117 bytes)

You can find this article also on the ftp-server of The MIT Press (access may be faster from some sites).

Self citation

    @article{jflp97-07,
      author={Puri Arenas-S\'{a}nchez and Agostino Dovier},
      title={A Minimality Study for Set Unification},
      journal={Journal of Functional and Logic Programming},
      volume={1997},
      number={7},
      publisher={The MIT Press},
      month={December},
      year={1997}
    }

Main page