Summary

Form the point of view of formal languages, natural languages contain context-sensitive productions (i.e. the realization of the surface structure of an agent in relation to the position of the predicate) as well as narrowing (=unrestricted) productions (i.e. elliptical constructs). Yet even in the best case, available parsers only cope with all context-free grammars (Early/CKY). A goal of this project is to find out the conditions for the realizablility of a parser for unrestricted grammars (Chomsky-0 type).

The simple basic idea of this parser is the derivation of the language up to a certain depth, the storage of the word and their derivation graphs in a database, and the lookup of these graphs in the case of a parse request. Form the formal point of view, this approach makes the parser even weaker than a simple final acceptor, since the parseable language is finite. Yet, the approach enables the usage of arbitrary productions in a grammar. For certain problem domains this might be an advantage. The precondition for the applicability of this approach is an arbitrary but certain limit for a) the word lengths and b) the inherent complexity of the deduction. The two main questions to be answered by this research project is whether the assumption of such a limit is valid for natural languages, and whether this limit is reachable with the given approach on current computer systems.