So far, we only have required that the value of the essential feature should be instantiated. However, it has not been specified what exactly this means. Informally, it can be specified like ``show me all signs that place exactly the following constraints on the following semantic representation.'' ([VanNoord1993], page 56) or string. That is, we want our algorithm to enumerate all possible feature structures that have a compatible value for the value of essential feature. Thus if we want to parse a string, we want the feature structure of that string and analogously for generation we want a feature structure of the input semantics. In the case of parsing, this restriction is implicitly obtained, if the string is represented as a proper list and contains no variables.
In [Wedekind1988] a formalization of such a criterion has been
given for generation, under the term of coherence and
completeness. Let be the semantic expression of the goal
constraint
and
the semantic expression of the
answer constraint
. Then a generator is said to be coherent if
subsumes
, and complete if
subsumes
. In other words, a generator is said to be
complete if all information of the goal semantic expression is
considered and it is coherent, if the generator does not add additional
semantic information during processing.
Van Noord has generalized this notation under the term
p-parsing problem, where parsing in this sense is the general
notation for parsing of a string and generation of a semantic
expression. He gives the following definition. Let the restriction
of a constraint with respect to a path p, written as
defined as follows:
Then the p-parsing problem consists of a grammar G and a goal q such that
A answer to a p-parsing problem is a solved constraint such
that
In our terminology the path p corresponds to the essential feature . Thus we also use the term -proof problem to indicate that parsing and generation are proofs of goals in which the value of the essential feature is instantiated.