English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We investigate the impact of modifying the constraining relations of aConstraint Satisfaction Problem (CSP) instance, with a fixed template, on theset of solutions of the instance. More precisely we investigate sensitiveinstances: an instance of the CSP is called sensitive, if removing any tuplefrom any constraining relation invalidates some solution of the instance.Equivalently, one could require that every tuple from any one of itsconstraints extends to a solution of the instance.  Clearly, any non-trivial template has instances which are not sensitive.Therefore we follow the direction proposed (in the context of strict width) byFeder and Vardi (SICOMP 1999) and require that only the instances produced by alocal consistency checking algorithm are sensitive. In the language of thealgebraic approach to the CSP we show that a finite idempotent algebra$\mathbf{A}$ has a $k+2$ variable near unanimity term operation if and only ifany instance that results from running the $(k, k+1)$-consistency algorithm onan instance over $\mathbf{A}^2$ is sensitive.  A version of our result, without idempotency but with the sensitivitycondition holding in a variety of algebras, settles a question posed by G.Bergman about systems of projections of algebras that arise from somesubalgebra of a finite product of algebras.  Our results hold for infinite (albeit in the case of $\mathbf{A}$ idempotent)algebras as well and exhibit a surprising similarity to the strict width $k$condition proposed by Feder and Vardi. Both conditions can be characterized bythe existence of a near unanimity operation, but the arities of the operationsdiffer by 1.

Sensitive instances of the Constraint Satisfaction Problem