We study query containment in three closely related formalisms: monadic disjunctive Datalog (MDDLog), MMSNP (a logical generalization of constraint satisfaction problems), and ontology-mediated queries (OMQs) based on expressive description logics and unions of conjunctive queries. Containment in MMSNP was known to be decidable due to a result by Feder and Vardi, but its exact complexity has remained open. We prove 2NExpTime-completeness and extend this result to monadic disjunctive Datalog and to OMQs.

CSP instances are commonly solved by backtracking search combined with constraint propagation. During search, constraint solvers aim to remove any literals (variable-value pair) that can be shown not to be part of any solution. This literal removal, called propagation, is the beating heart of modern constraint solvers. A significant proportion of the runtime of propagating constraint solvers is spent running propagation algorithms. Therefore any mechanism for reducing how frequently propagators are called leads directly to significant performance improvements.

Symmetries are common in many constraint problems. They can be broken statically or dynamically. The focus of this paper is the symmetry breaking during search (SBDS) method that adds conditional symmetry breaking constraints upon each backtracking during search. To trade completeness for efficiency, partial SBDS (ParSBDS) is proposed by posting only a subset of symmetries. We propose an adaptation method recursive SBDS (ReSBDS) of ParSBDS which extends ParSBDS to break more symmetry compositions. We observe that the symmetry breaking constraints added for each symmetry at a search node are nogoods and increasing. A global constraint (incNGs), which is logically equivalent to a set of increasing nogoods, is derived. To further trade pruning power for efficiency, we propose weak-nogood consistency (WNC) for nogoods and a lazy propagator for SBDS (and its variants) using watched literal technology. We further define generalized weak-incNGs consistency (GWIC) for a conjunction of increasing nogoods, and give a lazy propagator for incNGs.

RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. We focus on efficiently characterizing non-redundant constraints in large real world RCC8 networks and obtaining their prime networks. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N. A prime network of N is a network which contains no redundant constraints, but has the same solution set as N. We make use of a particular partial consistency, namely, G-path consistency, and obtain new complexity results for various cases of RCC8 networks, while we also show that given a maximal distributive subclass for RCC8 and a network N defined on that subclass, the prunning capacity of G-path consistency and path consistency is identical on the common edges of G and the complete graph of N, when G is a triangulation of the constraint graph of N. Finally, we devise an algorithm based on G-path consistency to compute the unique prime network of a RCC8 network, and show that it significantly progresses the state-of-the-art for practical reasoning with real RCC8 networks scaling up to millions of nodes.

Formal Concept Analysis (FCA) is a prominent field of applied mathematics using object-attribute relationships to define formal concepts -- groups of objects with common attributes -- which can be ordered into conceptual hierarchies, so-called concept lattices. We consider the problem of satisfiability of membership constraints, i.e., to determine if a formal concept exists whose object and attribute set include certain elements and exclude others. We analyze the computational complexity of this problem in general and for restricted forms of membership constraints. We perform the same analysis for generalizations of FCA to incidence structures of arity three (objects, attributes and conditions) and higher. We present a generic answer set programming (ASP) encoding of the membership constraint satisfaction problem, which allows for deploying available highly optimized ASP tools for its solution. Finally, we discuss the importance of membership constraints in the context of navigational approaches to data analysis.

The tastes of a user can be represented in a natural way by using qualitative preferences. In this paper, we explore how ontological knowledge expressed via existential rules can be combined with CP-theories to (i) represent qualitative preferences along with domain knowledge, and (ii) perform preference-based answering of conjunctive queries (CQs). We call these combinations ontological CP-theories (OCP-theories). We define skyline and k-rank answers to CQs based on the user's preferences encoded in an OCP-theory, and provide an algorithm for computing them. We also provide precise complexity (including data tractability) results for deciding consistency, dominance, and CQ skyline membership for OCP-theories.

In this paper, we propose a qualitative formalism for representing and reasoning about time at different scales. It extends the algebra of Euzenat and overcomes its major limitations, allowing one to reason about relations between points and intervals. Our approach is more expressive than the other algebras of temporal relations: for instance, some relations are more relaxed than those in Allen's algebra, while others are stricter. In particular, it enables the modeling of imprecise, gradual, or intuitive relations, such as "just before" or "almost meet." In addition, we give several results about how a relation changes when considered at different granularities. Finally, we provide an algorithm to compute the algebraic closure of a temporal constraint network in our formalism, which can be used to check its consistency.

Probabilistic sentential decision diagrams (PSDDs) are a tractable representation of structured probability spaces, which are characterized by complex logical constraints on what constitutes a possible world. We develop general-purpose techniques for probabilistic reasoning and learning with PSDDs, allowing one to compute the probabilities of arbitrary logical formulas and to learn PSDDs from incomplete data. We illustrate the effectiveness of these techniques in the context of learning preference distributions, to which considerable work has been devoted in the past. We show, analytically and empirically, that our proposed framework is general enough to support diverse and complex data and query types. In particular, we show that it can learn maximum-likelihood models from partial rankings, pairwise preferences, and arbitrary preference constraints. Moreover, we show that it can efficiently answer many queries exactly, from expected and most likely rankings, to the probability of pairwise preferences, and diversified recommendations. This case study illustrates the effectiveness and flexibility of the developed PSDD framework as a domain-independent tool for learning and reasoning with structured probability spaces.

Wireless sensor networks are being increasingly used for sustainable development. The task of routing in these resource-constraint networks is particularly challenging as they operate over prolonged deployment periods, necessitating optimal use of their resources. Moreover, due to the deployment in unattended environments, they become an easy target for attackers. In this paper, we propose a hierarchical POMDP based approach to make routing decisions with partial/limited information about the sensor nodes, in a secure and energy-efficient manner. We demonstrate in a large-scale simulation that the approach provides a better energy/packet delivery tradeoff than competing methods, and also validate these conclusions in a real-world testbed.

In particular, so-called 1/fα noise series with α close to 1 (also called pink noise) occur in sound, music and countless human artifacts or natural events, from the fluctuations of the flood levels of the Nile to movements of the stock market. As a consequence, many generative models for 1/f noise have been designed to produce series that look or sound "natural" or "human". In this paper, we formulate the generation of 1/f series as a hard constraint satisfaction problem, so that 1/f noise generation can be used as an add-on to arbitrary sequence generation problems. We take inspiration from a simple yet beautiful stochastic algorithm invented by Voss and introduce the Voss constraint. We show that Voss' algorithm can be modeled as a tree of ternary sum constraints, leading to efficient filtering. We illustrate our constraint with a melody generation problem, and show that the addition of the Voss constraint tends indeed to produce sequences whose spectrum have a 1/f distribution, regardless of the other constraints of the problem. We discuss the advantages and limitations of this approach and possible extensions.