JFLP: Volume 1996, Article 2

The Journal of Functional and Logic Programming

Volume 1996

Article 2

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

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

Implementation of a Deterministic Partial E -Unification Algorithm for Macro Tree Transducers

Heinz Faßbender, Andrea Mössle , and Heiko Vogler ,

26 May 1996

Abstract

During the execution of functional logic programs, particular E -unification problems must be solved quite frequently. In this paper we contribute to the efficient solution of such problems in the case where E is induced by particular term rewriting systems called macro tree transducers. We formalize the implementation of a deterministic partial E -unification algorithm on a deterministic abstract machine, called the twin unification machine. The unification algorithm is based on a particular narrowing strategy that combines leftmost outermost narrowing with a local constructor consistency check and a particular occur check. The twin unification machine uses two runtime stacks; it is an extension of an efficient leftmost outermost reduction machine for macro tree transducers. The feasibility of the presented implementation technique is proved by an implementation that has been developed on a SPARCstation SLC.

The following versions of the article are available:

• Preformatted versions of the article (compressed with gzip )
  • DVI (94 kb)
  • PostScript (184 kb)
• Source materials for custom formatting
  • LaTeX ( JFLP-A96-02.tex , 50 kb)
  • BIBTeX ( JFLP-A96-02.bib , 3 kb)
  • PostScript Figure ( JFLP-A96-02-f1.ps.gz , 3 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{jflp96-02,
      author={Heinz Fa{\ss}bender and Andrea M{\"o}ssle and Heiko Vogler},
      title={Implementation of a Deterministic Partial \(E\)-Unification
        Algorithm for Macro Tree Transducers},
      journal={Journal of Functional and Logic Programming},
      volume={1996},
      number={2},
      publisher={The MIT Press},
      month={May},
      year={1996}
    }

Main page