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 study the problem of enumerating the satisfying assignments for circuitclasses from knowledge compilation, where assignments are ranked in a specificorder. In particular, we show how this problem can be used to efficientlyperform ranked enumeration of the answers to MSO queries over trees, with theorder being given by a ranking function satisfying a subset-monotonicityproperty.  Assuming that the number of variables is constant, we show that we canenumerate the satisfying assignments in ranked order for so-called multivaluedcircuits that are smooth, decomposable, and in negation normal form (smoothmultivalued DNNF). There is no preprocessing and the enumeration delay islinear in the size of the circuit times the number of values, plus alogarithmic term in the number of assignments produced so far. If we furtherassume that the circuit is deterministic (smooth multivalued d-DNNF), we canachieve linear-time preprocessing in the circuit, and the delay only featuresthe logarithmic term.

Ranked Enumeration for MSO on Trees via Knowledge Compilation