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: 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}
    }

----------------------------------------------------------------

*back to* Main page