Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo khoa học: "Parsing for Semidirectional Lambek Grammar is NP-Complete"

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 nondirectional abstraction rule allowing the formula abstracted over to appear anywhere in the premise sequent's left-hand side, thus permitting non-peripheral extraction. SD[ grammars are able to generate each context-free language and more than that. We show that the parsing problem for semidireetional Lambek Grammar is NP-complete by a reduction of the 3Partition problem. . | Parsing for Semidirectional Lambek Grammar is NP-Complete Jochen Dorre Institut fiir 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 SDL there is an additional non-directional abstraction rule allowing the formula abstracted over to appear anywhere in the premise sequent s left-hand side thus permitting non-peripheral extraction. SDL grammars are able to generate each context-free language and more than that. We show that the parsing problem for semidirectional 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 languages LCG is superior to CG in that it can cope in a natural way with extraction and unbounded dependency phenomena. For instance no special category assignments need to be stipulated to handle a relative clause containing a trace because it is analyzed via hypothetical reasoning like a traceless clause with the trace being the hypothesis to be discharged when combined with the relative pronoun. Figure 1 illustrates this proof-logical behaviour. Notice that this natural-deduction-style proof in the type logic corresponds very closely to the phrasestructure tree one would like to adopt in an .