Font Size:

Combinators’ Introduction: an Enhanced Algorithm

Last modified: 2009-03-18

#### Abstract

Strategies for removal and introduction of combinators are very important to assure an accurate use of combinatory logic and combinators in natural language processing, especially in structural reorganization of expressions that express semantic interpretation. Such a strategy already exists for the elimination of combinators in a combinatory expression to obtain a normal form without combinators, but none existed to automate the inverse process. In our previous work, we addressed this problem by proposing an algorithm for the automation of combinators’ introduction, which finds the introduction level and introduces it at the first available spot. However, this algorithm shows its limits. There are some specific cases where a combinator can be introduced at more than one place. We needed to improve our algorithm so that it can automatically find the exact path to take in order to reach the correct place where we have to introduce the combinator, and then the algorithm would work for any combinatory expression. This paper presents the enhanced algorithm with an example of its execution.

Full Text:
PDF