The interface between phrasal and functional constraints

Many modern grammatical formalisms divide the task of linguistic specification into a context-free component of phrasal constraints and a separate component of attribute-value or functional constraints. Conventional methods for recognizing the strings of a language also divide into two parts so that they can exploit the different computational properties of these components. This • paper focuses on the interface between these components as a source of computational complexity distinct from the complexity internal to each. We first analyze the common hybrid strategy in which a polynomial context-free parser is modified to interleave functional constraint solving with context-free constituent analysis. This strategy depends on the property of monotonicity in order to prune unnecessary computation. We describe a number of other properties that can be exploited for computational advantage, and we analyze some alternative interface strategies based on them. We present the results of preliminary experiments that generally support our intuitive analyses. A surprising outcome is that under certain circumstances an algorithm that does no pruning in the interface may perform significantly better than one that does.