  We study the problem of enumerating the satisfying assignments for circuit
classes from knowledge compilation, where assignments are ranked in a specific
order. In particular, we show how this problem can be used to efficiently
perform ranked enumeration of the answers to MSO queries over trees, with the
order being given by a ranking function satisfying a subset-monotonicity
property.
  Assuming that the number of variables is constant, we show that we can
enumerate the satisfying assignments in ranked order for so-called multivalued
circuits that are smooth, decomposable, and in negation normal form (smooth
multivalued DNNF). There is no preprocessing and the enumeration delay is
linear in the size of the circuit times the number of values, plus a
logarithmic term in the number of assignments produced so far. If we further
assume that the circuit is deterministic (smooth multivalued d-DNNF), we can
achieve linear-time preprocessing in the circuit, and the delay only features
the logarithmic term.
