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/

Zendy Plus

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

Zendy Tools

Zendy Open

The tractability of certain CSPs for dense or sparse instances is known fromthe 90s. Recently, the densification and the sparsification of CSPs wereformulated as computational tasks and the systematical study of theircomputational complexity was initiated.  We approach this problem by introducing the densification operator, i.e. theclosure operator that, given an instance of a CSP, outputs all constraints thatare satisfied by all of its solutions. According to the Galois theory ofclosure operators, any such operator is related to a certain implicationalsystem (or, a functional dependency) $\Sigma$. We are specifically interestedin those classes of fixed-template CSPs, parameterized by constraint languages$\Gamma$, for which there is an implicational system $\Sigma$ whose size is apolynomial in the number of variables $n$. We show that in the Boolean case,such implicational systems exist if and only if $\Gamma$ is of bounded width.For such languages, $\Sigma$ can be computed in log-space or in a logarithmictime with a polynomial number of processors. Given an implicational system$\Sigma$, the densification task is equivalent to the computation of theclosure of input constraints. The sparsification task is equivalent to thecomputation of the minimal key.

The algebraic structure of the densification and the sparsification tasks for CSPs