next up previous
Next: Undecidability Up: On the Intersection of Previous: The intersection of a

The intersection of a DCG and a FSA

First note that the problem of calculating the intersection of a DCG and a FSA can be solved trivially by a generalization of the construction used by [1]. However, if we use that method we will end up with an enormously large forest grammar that is not even guaranteed to contain solutions. Therefore, we are interested in methods that only generate a small subset of this; if the intersection is empty we want an empty parse-forest grammar. The straightforward approach is to generalize existing recognition algorithms.

The same techniques that are used for calculating the intersection of a FSA and a CFG can be applied in the case of DCGs. In order to compute the intersection of a DCG and a FSA we assume that FSA's are represented as before. DCGs are represented using the same notation we used for context-free grammars, but now of course the category symbols can be first-order terms of arbitrary complexity (note that without loss of generality we don't take into account DCGs having external actions defined in curly braces).




next up previous
Next: Undecidability Up: On the Intersection of Previous: The intersection of a
Noord G.J.M. van
1998-09-29