Coherence and completeness as required by the -proof problem (see section 3.4) is handled in the following way. Note that the -proof problem requires that only and all elements of the input are considered during a proof. The coherence part means that during processing no additional information may be added. To ensure this property, we actually perform scanning in a two step approach. If scanning is tried for some selected element, we first perform a lexical lookup using the first element of the string (i.e., the value of the essential feature) or the current value of the predicate of the lexicon. This is meaningful, since lexical entries are inserted into the lexicon using exactly this information as a key. Thus if lexicon lookup fails the scanning process also fails for this selected element. However, if possible lexical entries can be retrieved we unify them with the constraints of the current selected element. The advantage of performing scanning in this two step way, is that (a) we immediately know of some information in the input which is not valid, (b) that we also can process multiple word entries, and (c) that we only consider information present in the input. Since, it might be the case that some lexical entries do not have a semantic information we require that these entries have a semantic value *nil defining the ``null'' semantics.
Completeness is checked easily as follows. Note that we require that the reduced start item should be added to the initial item set. However, this is only possible if the value of the essential feature is identical to the input (which has been used to define the index of the initial item set). Thus if we know that the initial item set does not contain an answer we reject the query, even in the case that some other item sets contain an answer.