p, called TokenLabel, which returns the label of a fixed token t. Then, Dp comprises of all x **which have the**
token t, and Rp is the set of all labels. Thus, if x ∈ Dp**, then**

$$p({\bf x},y_{c},c)\triangleq\left\{\begin{array}{ll}y_{c}&{\bf x}_{c}=t\\ \bot&\mbox{otherwise}\end{array}\right.\tag{8}$$

and, given y and x ∈ Dp,

$$p({\bf x},{\bf y})\triangleq\left\{\begin{array}{ll}y&\mbox{all occurrences of$t$in${\bf x}$are labeled with label$y$}\\ \perp&\mbox{otherwise}\end{array}\right.\tag{9}$$

Example 2 **Next consider a more complex example that allows us to express regularity in the order of labels**
in a collection of bibliography records. Let x be a publications record and y **its labeling. Define property** p, called NextLabel, which returns the first non-Other label in y **after a Title. A special label 'End' marks the**
end of y. So Rp **contains 'End' and all labels except Other. Thus,**

$$p(\mathbf{x},y_{c},c)\triangleq{\left\{\begin{array}{l l}{\beta}&{y_{c}=\mathrm{Title}\wedge y_{c+i}=\beta\land(\forall j:0<j<i:y_{c+j}=\mathrm{Other})}\\ {\mathrm{End}}&{y_{c}=\mathrm{Title}\wedge c\text{isthelastcliquein}\mathbf{y}}\\ {\bot}&{y_{c}\neq\mathrm{Title}}\end{array}\right.}$$
$$\left(10\right)$$

Therefore,

$$p(\mathbf{x},\mathbf{y})\triangleq{\left\{\begin{array}{l l}{\varnothing}\\ {\beta}\\ {\bot}\end{array}\right.}$$
∅ y **has no Title**
 -  $\beta$ is the first non-Other label following **each** Tittle in **y**  - otherwise  -
$$(11)$$

Example 3 In both the above examples the range R′p **of the properties was labels. Consider a third property,**
called BeforeToken **whose range is the space of tokens. This property returns the identity of the token before**
a Title in y**. So,**

$$p(\mathbf{x},y_{c},c)\triangleq{\left\{\begin{array}{l l}{x_{c-1}}&{y_{c}={\mathrm{Title}}\land(c>0)}\\ {}&{}\\ {\mathrm{`Start'}}&{y_{c}={\mathrm{Title}}\land(c=0)}\\ {\bot}&{y_{c}\neq{\mathrm{Title}}}\end{array}\right.}$$
$$\left(12\right)$$

Therefore,

$p(\mathbf{x},\mathbf{y})\triangleq\begin{cases}\varnothing&\text{No Title in}\mathbf{y}\\\\ \mathbf{\text{`Start'}}&\text{The only Title in}\mathbf{y}\text{is at the beginning of}\mathbf{y}\\\\ t&\text{All Tildes in}\mathbf{y}\text{are preceded by token}t\\\\ \bot&\mathbf{y}\text{has two or more Tildes with different preceding tokens}\end{cases}$
$$(13)$$
Some important families of symmetric clique potentials have been described in [10], and recalled in Section 3.

We use two most widely used of those families, called Potts and majority**, defined as:**

$$\begin{array}{rcl}\mbox{C}^{\rm Potts}\big{(}\{v_{1},\ldots,v_{n}\}\big{)}&\triangleq&\lambda\sum_{v^{\prime}}n_{v^{\prime}}^{2}\\ \mbox{C}^{\rm Maj}\big{(}\{v_{1},\ldots,v_{n}\}\big{)}&\triangleq&\sum_{v^{\prime}}w_{\hat{v}v^{\prime}}n_{v^{\prime}},\ \ \hat{v}=\mbox{argmax}_{v}n_{v}\end{array}$$

where nv is frequency of v in the multiset {v1, . . . , vn} and λ, w **are fixed parameters of the potentials.**