14199573
Zapato: Automatic Theorem Proving for Predicate Abstraction Refinement
Counterexample-driven abstraction refinement is an automatic process that produces abstract models of finite and infinite-state systems. When this process is applied to software, an automatic theorem prover for quantifier-free first-order logic helps to determine the feasibility of program paths and to refine the abstraction. In this paper we report on a fast, lightweight, and automatic theorem prover called Zapato which we have built specifically to solve the queries produced during the abstraction refinement process.
11375306
A solver for quantified Boolean and linear constraints
We make a number of contributions to the understanding and practical resolution of quantified constraints. Unlike previous work in the CP literature that was essentially focused on constraints expressed as binary tables, we focus on Presburger Arithmetics, i.e., Boolean combinations of linear constraints. From a theoretical perspective, we clarify the problem of the treatment of universal quantifiers by proposing a "symmetric" version of the notion of quantified consistency. This notion imposes to maintain two constraint stores, which will be used to reason on universal and existential variables, respectively. We then describe a branch & bound algorithm that integrates both forms of propagation. Its implementation is, to the best of our knowledge, the first CP solver for this class of quantified constraints.
14923930
Cache Performance of SAT Solvers: a Case Study for Efficient Implementation of Algorithms
We experimentally evaluate the cache performance of different SAT solvers as a case study for the efficient implementation of SAT algorithms. We evaluate several different Boolean Constraint Propagation (BCP) mechanisms and show their respective run time and cache performances on selected benchmark instances. From the experiments we conclude that a cache friendly data structure is a key element in the efficient implementation of SAT solvers. We also show empirical cache miss rates of several modern SAT solvers based on the Davis-Logemann-Loveland (DLL) algorithm with learning and non-chronological backtracking. We conclude that the recently developed SAT solvers are much more cache friendly in data structures and algorithm implementations compared with their predecessors.
18035076
On Subsumption Removal and On-the-Fly CNF Simplification
CNF Boolean formulas generated from resolution or solution enumeration often have much redundancy. Efficient algorithms are needed to simplify and compact such CNF formulas. In this paper, we present a novel algorithm to maintain a subsumption-free CNF clause database by efficiently detecting and removing subsumption as the clauses are being added. We then present an algorithm that compact CNF formula further by applying resolutions to make it Decremental Resolution Free. Our experimental evaluations show that these algorithms are efficient and effective in practice.
6734525
Propositional Satisfiability and Constraint Programming: A comparative survey
Propositional Satisfiability (SAT) and Constraint Programming (CP) have developed as two relatively independent threads of research cross-fertilizing occasionally. These two approaches to problem solving have a lot in common as evidenced by similar ideas underlying the branch and prune algorithms that are most successful at solving both kinds of problems. They also exhibit differences in the way they are used to state and solve problems since SAT's approach is, in general, a black-box approach, while CP aims at being tunable and programmable. This survey overviews the two areas in a comparative way, emphasizing the similarities and differences between the two and the points where we feel that one technology can benefit from ideas or experience acquired from the other.
9292941
Chaff: engineering an efficient SAT solver
Boolean satisfiability is probably the most studied of the combinatorial optimization/search problems. Significant effort has been devoted to trying to provide practical solutions to this problem for problem instances encountered in a range of applications in electronic design automation (EDA), as well as in artificial intelligence (AI). This study has culminated in the development of several SAT packages, both proprietary and in the public domain (e.g. GRASP, SATO) which find significant use in both research and industry. Most existing complete solvers are variants of the Davis-Putnam (DP) search algorithm. In this paper we describe the development of a new complete solver, Chaff which achieves significant performance gains through careful engineering of all aspects of the search-especially a particularly efficient implementation of Boolean constraint propagation (BCP) and a novel low overhead decision strategy. Chaff has been able to obtain one to two orders of magnitude performance improvement on difficult SAT benchmarks in comparison with other solvers (DP or otherwise), including GRASP and SATO.
6285526
A configuration management system supporting component-based software development
Component-based software development has been viewed as an emerging paradigm of software development. This paper analyzes the requirements of configuration management in component-based development process. Based on the analysis, a prototype configuration management system is proposed to meet the requirements. An example of using the system is also given.
9540989
Word Graphs: The Third Set
This is the third paper in a series of natural language processing in term of knowledge graphs. A word is a basic unit in natural language processing. This is why we study word graphs. Word graphs were already built for prepositions and adwords (including adjectives, adverbs and Chinese quantity words) in two other papers [2], [3]. In this paper, we propose the concept of the logic word and classify logic words into groups in terms of semantics and the way they are used in describing reasoning processes.
15420689
Similarity space projection for web image search and annotation
Web image search has been explored and developed in academic as well as commercial areas for over a decade. To measure the similarity between Web images and user queries, most of the existing Web image search systems try to convert an image to textual keywords by analyzing the textual information available (such as surrounding text and image filename) with or without leveraging image visual features (such as color, texture, shape). In this way, the existing systems transform "Web images" to the "query (text)" space so as to compare the relevance of images to the query. In this paper, we present a novel solution to Web image search - similarity space projection (SSP). This algorithm takes images and queries as two heterogeneous object peers, and projects them into a third Euclidean "similarity space" in which their similarity can be directly measured. The rule of projection guarantees that in the new space the relevant images are kept close to the corresponding query and those irrelevant ones are away from it. Experiments on real-world Web image collections showed that the proposed algorithm significantly outperformed traditional information retrieval models (such as vector space model) in the application of image search. Besides Web image search, we demonstrate that this algorithm can also be applied to image annotation scenario, and has promising performance. Thus, this algorithm unifies Web image search and image annotation into same framework.
13998980
Image annotation refinement using random walk with restarts
Image annotation plays an important role in image retrieval and management. However, the results of the state-of-the-art image annotation methods are often unsatisfactory. Therefore, it is necessary to refine the imprecise annotations obtained by existing annotation methods. In this paper, a novel approach to automatically refine the original annotations of images is proposed. On the one hand, for Web images, textual information, e.g. file name and surrounding text, is used to retrieve a set of candidate annotations. On the other hand, for non-Web images that are lack of textual information, a relevance model-based algorithm using visual information is used to decide the candidate annotations. Then, candidate annotations are re-ranked and only the top ones are reserved as the final annotations. To re-rank the annotations, an algorithm using Random Walk with Restarts (RWR) is proposed to leverage both the corpus information and the original confidence information of the annotations. Experimental results on both non-Web images of Corel dataset and Web images of photo forum sites demonstrate the effectiveness of the proposed method.
13978949
An experimental study of two graph analysis based component capture methods for object-oriented systems
The problem of how to partition a software system and thus capture its overall architecture and its constituent components has become a research focus in the community of software engineering. In the literature, many methods have been proposed for solving this problem. For example, both top-down and bottom-up methods based on analyzing the graph representation of software systems have been proposed. We report an experimental study of a top-down method and a bottom-up method. In our study, we focus on the capability of component capture, the capability of architecture recovery and the time complexity for the two methods. According to our results on two real world systems, the studied bottom-up method is superior to the studied top-down method in both aspects, although the time complexity of the bottom-up method remains a big concern for large systems.