, where:
Maruyama developed a new grammar called Constraint Dependency
Grammar (CDG) [Maruyama, 1990a, Maruyama, 1990b, Maruyama, 1990c].
He then showed how CDG parsing can be cast as a CSP with a finite
domain, so constraints can be used to rule out ungrammatical sentences.
A CDG is a four-tuple,
, where:
A sentence 
is a string
of length n. For each word 
of a sentence s, we must keep
track of p different roles (or variables). A role is a variable which takes on
role values of the form <l,m>,
where 
and 
. Role values are
denoted in examples as label-modifiee. In parsing,
each label in L indicates a different syntactic function.
The value of m in the role value <l,m>, when assigned to a
particular role of 
, specifies the position of the word that
is modifying when it takes on the function specified by the
label, l (e.g., subj-3 indicates that the word with that label is
a subject when it modifies the third word in the sentence).
The sentence s is said to be
generated by the grammar G if there exists an assignment A
which maps a role value to each of the n*p roles for s such that
the constraint set C (described in the next paragraph) is satisfied.
A constraint set is a logical formula of the
form:
,
where each 
ranges over all of the role values in each of the roles
for each word of s.
Each subformula P 
in C must be of the form: (if Antecedent Consequent),
where Antecedent and Consequent are
predicates or predicates joined by the logical connectives.
Below are the basic components used to express constraints.
, 
, 
(a=2 in [Maruyama, 1990a]).
L R
{nil, 1, 2, , n}, where n corresponds to the number of words in a sentence. )
for the word at position y.
A subformula P is called a
unary constraint if it contains one variable and a binary
constraint if it contains two.
A CDG grammar has two associated parameters,
degree and arity. The degree of a grammar G is the number of roles.
The arity of the grammar, a, corresponds to the maximum number of
variables in the subformulas of C.
Consider the example grammar, 
, which is defined
using the following four-tuple:
, 
, 
(see constraints in 
. has a degree of one and an arity of two. To
illustrate the process of parsing with constraint satisfaction,
Figure 6 shows the steps for parsing the sentence
The dog eats. To simplify the presentation of this example, the
grammar uses a single role, the governor role, which is
denoted as G in the constraint network in Figure 6.
The governor role indicates the function a word fills in a
sentence when it is governed by its head word. A word is called the
head of a phrase when it forms the basis of the phrase (e.g.,
the verb is the head of the sentence). In useful
grammars, we would also include several
needs roles (e.g, need1, need2) to make certain that a head word has
all of the constituents it needs to be complete (e.g., a singular
count noun needs a determiner to be a complete noun phrase).
Figure 6: Using constraints to parse the sentence: The dog eats.
To determine whether the sentence, The dog eats,
is generated by the grammar, the CDG
parser must be able to assign at least one role value to each of the n * p roles that satisfies
the grammar constraints (n=3 is
sentence length, and p=1 is the number of roles). Because the
values for a role are selected from the finite set 
{nil, 1, 2, 3}, CDG parsing can be viewed as a
constraint satisfaction problem over a finite domain. Therefore,
constraint satisfaction can be used to
determine the possible parses of this sentence.
Initially, for each word, all possible role values are assigned to the governor role. We assume that a word must either modify another word (other than itself) or modify no word (m=nil). Nothing is gained in CDG by having a word modify itself. Next the unary constraints are applied to all of the role values in the constraint network. A role value is incompatible with a unary constraint if and only if it satisfies the antecedent, but not the consequent. Notice in Figure 6 that all the role values associated with the governor role of the first word (the) satisfy the antecedent of the first unary constraint, but det-nil, subj-nil, subj-2, subj-3, root-nil, root-2, and root-3 do not satisfy the consequent, and so they are incompatible with the constraint. When a role value violates a unary constraint, node consistency eliminates those role values from their role because they can never participate in a parse for the sentence. After all unary constraints are applied to the top constraint network in Figure 6, the second network is produced.
Next, binary constraints are applied. Binary constraints determine which pairs of role values can legally coexist. To keep track of pairs of role values, arcs are constructed connecting each role to all other roles in the network, and each arc has an associated arc matrix, whose row and column indices are the role values associated with the two roles it connects. The entries in an arc matrix can either be 1 (indicating that the two role values indexing the entry are compatible) or 0 (indicating that the role values cannot simultaneously exist). Initially, all entries in each matrix are set to 1, indicating that the pair of role values indexing the entry are initially compatible (because no constraints have been applied). In our example, the single binary constraint (shown in Figure 6) is applied to the pairs of role values indexing the entries in the matrices. For example, when x=det-3 for the and y=root-nil for eats, the consequent of the binary constraint fails; hence, the role values are incompatible. This is indicated by replacing the entry of 1 with 0.
Following the binary constraints, the roles of the constraint network can still contain role values which are incompatible with the parse for the sentence. Role values that are not supported by the binary constraints can be eliminated by achieving arc consistency. For example, det-3 for the is not supported by the remaining role value for eats and is thus deleted from the role.
After arc consistency, the example sentence has a single parse because there is only one value per role in the sentence. A parse for a sentence consists of an assignment of role values to roles such that the unary and binary constraints are satisfied for that assignment. In general, there can be more than one parse for a sentence; hence, there can be more than one assignment of values to the roles of the sentence. Note that the assignment for the example sentence is:
If there is only one possible sentence such that the part of speech of each of the words is known in advance, then the parsing problem can be cast as a CSP. However, for the ambiguity present in written and spoken sentences to be handled uniformly requires the use of MUSE CSP.