Redundancy checking is an important task in the research of knowledge representation and reasoning. In this paper, we consider redundant qualitative constraints. For a set ? of qualitative constraints, we say a constraint ( x R y ) in ? is redundant if it is entailed by the rest of ?. A prime subnetwork of ? is a subset of ? which contains no redundant constraints and has the same solution set as ?. It is natural to ask how to compute such a prime subnetwork, and when it is unique. We show that this problem is in general intractable, but becomes tractable if ? is over a tractable subalgebra S of a qualitative calculus. Furthermore, if S is a subalgebra of the Region Connection Calculus RCC8 in which weak composition distributes over nonempty intersections, then ? has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from ?. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal and globally consistent in a qualitative sense. A thorough empirical analysis of the prime subnetwork upon real geographical data sets demonstrates the approach is able to identify significantly more redundant constraints than previously proposed algorithms, especially in constraint networks with larger proportions of partial overlap relations.
Redundancy checking is an important task in AI research, in particular in knowledge representation and reasoning. For example, Ginsberg @cite_30 and Schmolze and Snyder @cite_48 designed algorithms for checking redundancy of knowledge bases; Gottlob and Ferm "u ller @cite_8 and Liberatore @cite_19 analysed the computational properties of removing redundancy from a clause and a CNF formula, respectively; and Grimm and Wissmann @cite_41 considered checking redundancy of ontologies.
@cite_30 @cite_8 @cite_41 @cite_48 @cite_19
2058793155 2912554127 2042719229 1681144494
A knowledge base is redundant if it contains parts that can be inferred from the rest of it. We study some problems related to the redundancy of a CNF formula. In particular, any CNF formula can be made irredundant by deleting some of its clauses: what results is an irredundant equivalent subset. We study the complexity of problems related to irredundant equivalent subsets: verification, checking existence of an irredundant equivalent subset with a given size, checking necessary and possible presence of clauses in irredundant equivalent subsets, and uniqueness. We also consider the problem of redundancy with different definitions of equivalence. Abstract Redundancy is an increasingly popular technique for reducing response times in computer systems, and there is a growing body of theoretical work seeking to analyze performance in systems with redundancy. The idea is to dispatch a job to multiple servers at the same time and wait for the first copy to complete service. Redundancy can help reduce response time because redundant jobs get to experience the shortest of multiple queueing times and potentially of multiple service times—but it can hurt jobs that are not redundant and must wait behind the redundant jobs’ extra copies. Thus in designing redundancy systems it is critical to find ways to leverage the potential benefits without incurring the potential costs. Scheduling represents one tool for maximizing the benefits of redundancy. In this paper we study three scheduling policies: First-Come First-Served (FCFS), Least Redundant First (LRF, under which less-redundant jobs have priority over more-redundant jobs), and Primaries First (PF, under which each job designates a “primary” copy, and all other copies have lowest priority). Our goal for each of these policies is to understand the marginal impact of redundancy: how much redundancy is needed to get the biggest benefit? We study this question analytically for LRF and FCFS, and via simulation for all three policies. One of our primary contributions is a surprisingly intricate proof that mean response time is convex as well as decreasing as the proportion of jobs that are redundant increases under LRF for exponential services. While response time under PF is also decreasing and appears to be convex as well, we find that, surprisingly, FCFS may be neither decreasing nor convex, depending on the parameter values. Thus, the scheduling policy is key in determining both whether redundancy helps and the marginal effects of adding more redundancy to the system. The so-called “redundancy-based” approach to question answering represents a successful strategy for mining answers to factoid questions such as “Who shot Abraham Lincolnq” from the World Wide Web. Through contrastive and ablation experiments with Aranea, a system that has performed well in several TREC QA evaluations, this work examines the underlying assumptions and principles behind redundancy-based techniques. Specifically, we develop two theses: that stable characteristics of data redundancy allow factoid systems to rely on external “black box” components, and that despite embodying a data-driven approach, redundancy-based methods encode a substantial amount of knowledge in the form of heuristics. Overall, this work attempts to address the broader question of “what really matters” and to provide guidance for future researchers. In this paper, we present a new way to preprocess Boolean formulae in Conjunctive Normal Form (CNF). In contrast to most of the current pre-processing techniques, our approach aims at improving the filtering power of the original clauses while producing a small number of additional and relevant clauses. More precisely, an incomplete redundancy check is performed on each original clauses through unit propagation, leading to either a sub-clause or to a new relevant one generated by the clause learning scheme. This preprocessor is empirically compared to the best existing one in terms of size reduction and the ability to improve a state-of-the-art satisfiability solver.