In a constraint satisfaction problem, the tightness of an individual constraint only describes the influence that the variables within its scope have on one another. Clusters provide a broader view; they are dense, tight subproblems within a problem. A set of clusters for a problem and the links between them provide an abstraction of it. That abstraction can be used to guide search, to curtail inference, and to provide explanations to the user. This work is a hybrid of global and local search, where local search creates an abstraction and then global search exploits it. Heuristics reference clusters to order variables and to propagate more thoughtfully with respect to them. Results are provided on a variety of challenging benchmark problems.

A problem that often arises in using abstraction is the generation of abstract states, called spurious states, that are—in the abstract space—reachable from some abstract image of a state s, but which have no corresponding state in the original space reachable from s. Spurious states can have a negative effect on pattern database sizes and heuristic quality. We formally define a property—the downward path preserving property (DPP)—that guarantees an abstraction has no spurious states. Analyzing the computational complexity of (i) testing the DPP property for a given state space and abstraction and of (ii) determining whether this property is achievable at all for a given state space, results in strong hardness theorems. On the positive side, we identify formal conditions under which finding DPP abstractions is tractable.

The exploration of complex interaction networks has attracted considerable interest in various fields, ranging from fundamental biology and medicine to statistical physics and information technology.  In -omics disciplines, significant progresses have been made in understanding the large-scale properties and the biological relevance of these interactions. Some properties such as scale-free distribution of nodes connectivity or centrality are aspects commonly described in such complex interaction systems. In many of these studies the analysis of network topology is complemented by a semantic analysis that may rely on  different labels associated to the interacting entities.   One of the bottleneck of these semantic analysis is that they  are computationally costly. In this paper we present a framework to explore abstraction of networks useful to speedup the computation  of ground network measures. Such abstraction mechanisms may be used to efficiently provide accurate approximations of ground network measures.

This article presents two new algorithms whose purpose is to maintain the Max-RPC domain filtering consistency during search with a minimal memory footprint and implementation effort. Both are sub-optimal algorithms that make use of support residues, a backtrack-stable and highly efficient data structure which was successfully used to develop the state-of-the-art AC-3rm algorithm. The two proposed algorithms, Max-RPCrm and L-Max-RPCrm are competitive with best, optimal Max-RPC algorithms, while being considerably simpler to implement. L-Max-RPCrm computes an approximation of the Max-RPC consistency, which is guaranteed to be strictly stronger than AC with the same space complexity and better worst-case time complexity than Max-RPCrm. In practice, the difference in filtering power between L-Max-RPCrm and standard Max-RPC is nearly indistinguishable on random problems. Max-RPCrm and L-Max-RPCrm are implemented into the Choco Constraint Solver through a strong consistency global constraint. This work opens new perspectives upon the development of strong consistency algorithms into constraint solvers.

In this paper, we propose a new approach for solving the SAT problem. This approach consists in representing SAT instances thanks to an undirected graph issued from a polynomial transformation from SAT to the CLIQUE problem. Considering this graph, we exploit well known properties of chordal graphs to manipulate the SAT instance. Firstly, these properties allow us to define a new class of SAT polynomial instances. Moreover, they allow us to rewrite SAT instances in disjunctions of smaller instances which could be significantly easier to solve.

Given a system design (SD), a key task is to optimize this design to reduce the probability of catastrophic failures. We consider the task of redesigning an SD to minimize the probability of particular faults by introducing components selected from a component library. We have implemented a General Redesign Engine (GRE), which uses model-based reasoning techniques and Boolean functional synthesis from component libraries, to automate redesign for combinational circuits. For a significant subset of observations leading to catastrophic (forbidden) modes we demonstrate that GRE trades off redesign cost for increased fault tolerance, and shows a significant advantage compared to the Triple-Modular Redundancy (TMR) method. Our algorithm has a wide application in AI, including automated software and hardware design, error detection, reconfiguration and recovery, and modular robotics.

LiveJournal is a social network journal service with focus on user interactions. As for many other online social networks, predicting potential friendships in the LiveJournal network is a problem of great practical interest. Previous work has shown that graph features extracted from the graph associated with the network are good predictors for friendship links. However, contrary to the intuition, user data (e.g., interests shared by two users) does not always improve the predictions obtained with graph features alone. This could be due to the fact that features constructed from a large number of user declared interests cannot capture the implicit semantic of the interests. To test this hypothesis, we use a clustering approach to build an interest ontology, and explore the ability of the ontology to improve the performance of learning algorithms at predicting friendship links, when interest-based features are used alone or in combination with graph-based features. The results show that ontology-based features can help improve the performance of several machine learning classifiers (in particular, random forest classifiers) at the task of predicting links in the LiveJournal social network.

Current research on qualitative spatial representation and reasoning mainly focuses on one single aspect of space. In real world applications, however, multiple spatial aspects are often involved simultaneously. This paper investigates problems arising in reasoning with combined topological and directional information. We use the RCC8 algebra and the Rectangle Algebra (RA) for expressing topological and directional information respectively. We give examples to show that the bipath-consistency algorithm BIPATH is incomplete for solving even basic RCC8 and RA constraints. If topological constraints are taken from some maximal tractable subclasses of RCC8, and directional constraints are taken from a subalgebra, termed DIR49, of RA, then we show that BIPATH is able to separate topological constraints from directional ones. This means, given a set of hybrid topological and directional constraints from the above subclasses of RCC8 and RA, we can transfer the joint satisfaction problem in polynomial time to two independent satisfaction problems in RCC8 and RA. For general RA constraints, we give a method to compute solutions that satisfy all topological constraints and approximately satisfy each RA constraint to any prescribed precision.

Practically all programming languages allow the programmer to split a program into several modules which brings along several advantages in software development. In this paper, we are interested in the area of answer-set programming where fully declarative and nonmonotonic languages are applied. In this context, obtaining a modular structure for programs is by no means straightforward since the output of an entire program cannot in general be composed from the output of its components. To better understand the effects of disjunctive information on modularity we restrict the scope of analysis to the case of disjunctive logic programs (DLPs) subject to stable-model semantics. We define the notion of a DLP-function, where a well-defined input/output interface is provided, and establish a novel module theorem which indicates the compositionality of stable-model semantics for DLP-functions. The module theorem extends the well-known splitting-set theorem and enables the decomposition of DLP-functions given their strongly connected components based on positive dependencies induced by rules. In this setting, it is also possible to split shared disjunctive rules among components using a generalized shifting technique. The concept of modular equivalence is introduced for the mutual comparison of DLP-functions using a generalization of a translation-based verification method.

This paper presents a multilayered architecture that enhances the capabilities of current QA systems and allows different types of complex questions or queries to be processed. The answers to these questions need to be gathered from factual information scattered throughout different documents. Specifically, we designed a specialized layer to process the different types of temporal questions. Complex temporal questions are first decomposed into simple questions, according to the temporal relations expressed in the original question. In the same way, the answers to the resulting simple questions are recomposed, fulfilling the temporal restrictions of the original complex question. A novel aspect of this approach resides in the decomposition which uses a minimal quantity of resources, with the final aim of obtaining a portable platform that is easily extensible to other languages. In this paper we also present a methodology for evaluation of the decomposition of the questions as well as the ability of the implemented temporal layer to perform at a multilingual level. The temporal layer was first performed for English, then evaluated and compared with: a) a general purpose QA system (F-measure 65.47% for QA plus English temporal layer vs. 38.01% for the general QA system), and b) a well-known QA system. Much better results were obtained for temporal questions with the multilayered system. This system was therefore extended to Spanish and very good results were again obtained in the evaluation (F-measure 40.36% for QA plus Spanish temporal layer vs. 22.94% for the general QA system).