  Valued constraint satisfaction problems with ordered variables (VCSPO) are a
special case of Valued CSPs in which variables are totally ordered and soft
constraints are imposed on tuples of variables that do not violate the order.
We study a restriction of VCSPO, in which soft constraints are imposed on a
segment of adjacent variables and a constraint language $\Gamma$ consists of
$\{0,1\}$-valued characteristic functions of predicates. This kind of
potentials generalizes the so-called pattern-based potentials, which were
applied in many tasks of structured prediction.
  For a constraint language $\Gamma$ we introduce a closure operator, $
\overline{\Gamma^{\cap}}\supseteq \Gamma$, and give examples of constraint
languages for which $|\overline{\Gamma^{\cap}}|$ is small. If all predicates in
$\Gamma$ are cartesian products, we show that the minimization of a generalized
pattern-based potential (or, the computation of its partition function) can be
made in ${\mathcal O}(|V|\cdot |D|^2 \cdot |\overline{\Gamma^{\cap}}|^2 )$
time, where $V$ is a set of variables, $D$ is a domain set. If, additionally,
only non-positive weights of constraints are allowed, the complexity of the
minimization task drops to ${\mathcal O}(|V|\cdot |\overline{\Gamma^{\cap}}|
\cdot |D| \cdot \max_{\rho\in \Gamma}\|\rho\|^2 )$ where $\|\rho\|$ is the
arity of $\rho\in \Gamma$. For a general language $\Gamma$ and non-positive
weights, the minimization task can be carried out in ${\mathcal O}(|V|\cdot
|\overline{\Gamma^{\cap}}|^2)$ time.
  We argue that in many natural cases $\overline{\Gamma^{\cap}}$ is of moderate
size, though in the worst case $|\overline{\Gamma^{\cap}}|$ can blow up and
depend exponentially on $\max_{\rho\in \Gamma}\|\rho\|$.

Artificial Intelligence