Parsing with Semidirectional Lambek Grammar is NP-Complete

Parsing for Semidirectional Lambek Grammar is NP-Complete Jochen Dfrre Institut ffir maschinelle Sprachverarbeitung University of Stuttgart Abstract We study the computational complexity of the parsing problem of a variant of Lambek Categorial Grammar that we call semidirectional. In semidirectional Lambek calculus SD[ there is an additional non- directional abstraction rule allowing the formula abstracted over to appear any- where in the premise sequent's left-hand side, thus permitting non-peripheral ex- traction. SD[ grammars are able to gen- erate each context-free language and more than that. We show that the parsing prob- lem for semidireetional Lambek Grammar is NP-complete by a reduction of the 3- Partition problem. Key words: computational complexity, Lambek Categorial Grammar 1 Introduction Categorial Grammar (CG) and in particular Lambek Categorial Grammar (LCG) have their well-known benefits for the formal treatment of natural language syntax and semantics. The most outstanding of these benefits is probably the fact that the specific way, how the complete grammar is encoded, namely in terms of 'combinatory potentials' of its words, gives us at the same time recipes for the construction of meanings, once the words have been combined with others to form larger linguistic entities. Although both frameworks are equivalent in weak generative capacity -- both derive exactly the context-free lan- guages --, LCG is superior to CG in that it can cope in a natural way with extraction and unbounded de- pendency phenomena. For instance, no special cate- gory assignments need to be stipulated to handle a relative clause containing a trace, because it is an- alyzed, via hypothetical reasoning, like a traceless clause with the trace being the hypothesis to be dis- charged when combined with the relative pronoun. Figure 1 illustrates this proof-logical behaviour. No- tice that this natural-deduction-style proof in the type logic corresponds very closely to the phrase- structure tree one would like to adopt in an analysis with traces. We thus can derive Bill misses ~ as an s from the hypothesis that there is a "phantom" np in the place of the trace. Discharging the hypoth- esis, indicated by index 1, results in Bill misses being analyzed as an s/np from zero hypotheses. Ob- serve, however, that such a bottom-up synthesis of a new unsaturated type is only required, if that type is to be consumed (as the antecedent of an impli- cation) by another type. Otherwise there would be a simpler proof without this abstraction. In our ex- ample the relative pronoun has such a complex type triggering an extraction. A drawback of the pure Lambek Calculus !_ is that it only allows for so-called 'peripheral extraction', i.e., in our example the trace should better be initial or final in the relative clause. This inflexibility of Lambek Calculus is one of the reasons why many researchers study richer systems today. For instance, the recent work by Moortgat (Moortgat 94) gives a systematic in-depth study of mixed Lambek systems, which integrate the systems L, NL, NLP, and LP. These ingredient systems are obtained by varying the …

Content truncated to 500 words