Computing a Partition Function of a Generalized Pattern-Based Energy over a Semiring

Research output: Contribution to journalArticlepeer-review


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 Γ 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 Γ we introduce a closure operator, Γ¯ ⊇ Γ , and give examples of constraint languages for which | Γ¯ | is small. If all predicates in Γ 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 O(| V| · | D| 2· | Γ¯ | 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 O(| V| · | Γ¯ | · | D| · maxϱΓ‖ ϱ‖ 2) where ‖ ϱ‖ is the arity of ϱ∈ Γ . For a general language Γ and non-positive weights, the minimization task can be carried out in O(| V| · | Γ¯ | 2) time. We argue that in many natural cases Γ¯ is of moderate size, though in the worst case | Γ¯ | can blow up and depend exponentially on maxϱΓ‖ ϱ‖ .

Original languageEnglish
JournalTheory of Computing Systems
Publication statusAccepted/In press - 2023


  • Conditional random fields
  • Maximum a posteriori (MAP)
  • Pattern-based potential
  • Valued constraint satisfaction

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics


Dive into the research topics of 'Computing a Partition Function of a Generalized Pattern-Based Energy over a Semiring'. Together they form a unique fingerprint.

Cite this