Document constraint descriptors are obtained from user signals. User signals are received indicating a set of attribute-value relations that can apply to documents. The user signals are used to obtain equivalent logical relations, and the logical relations are used to obtain the document constraint descriptor defining a set of one or more constraints equivalent to the logical relations. The user signals can be received through user interface circuitry of various types, including display/select user interfaces or a paper user interface in which a user marks a form that is scanned. The machine can be a portable computing device, a fixed computing device, or a multifunction device. The machine can also solve the set of constraints and can use the solution to obtain document references, such as Web URLs, indicating documents that satisfy the set of constraints. The user can then request more detail, or can obtain a printed version of a document.