基于一阶逻辑的可满足求解方法研究进展

基于命题逻辑的布尔可满足SAT存在描述能力弱、抽象层次低、求解复杂度高等问题,而基于一阶逻辑的可满足性模理论SMT采用高层建模语言,表达能力更强,更接近于字级设计,避免将问题转化到位级求解,在硬件RTL级验证、程序验证与实时系统验证等领域得到了广泛应用。针对近年来涌现的众多SMT求解方法,依据方法的求解方式进行了分类与对比。而后,对3种主流的求解方法Eager方法、Lazy方法和DPLL(T)方法的实现进行了概要介绍。最后,讨论了SMT求解方法当前所面临的主要挑战以及在SMT求解方面的一些研究成果,并对今后的研究进行了展望。     

Boosting complete techniques thanks to local search methods

In this paper, an efficient heuristic allowing one to localize inconsistent kernels in propositional knowledge‐bases is described. Then, it is shown that local search techniques can boost the performance of logically complete methods for SAT. More precisely, local search techniques can be used to guide the branching strategy of logically complete techniques like Davis and Putnam's one, giving rise to significant performance improvements, in particular when addressing locally inconsistent problems. Moreover, this approach appears very competitive in the context of consistent SAT instances, too. This revised version was published online in June 2006 with corrections to the Cover Date.     

On a decidable generalized quantifier logic corresponding to a decidable fragment of first-order logic

Van Lambalgen (1990) proposed a translation from a language containing a generalized quantifierQ into a first-order language enriched with a family of predicatesR _i, for every arityi (or an infinitary predicateR) which takesQxg(x, y₁,..., y_n) to x(R(x, y₁,..., y₁) (x,y₁,...,y_n)) (y ₁,...,y_n are precisely the free variables ofQx). The logic ofQ (without ordinary quantifiers) corresponds therefore to the fragment of first-order logic which contains only specially restricted quantification. We prove that it is decidable using the method of analytic tableaux. Related results were obtained by Andréka and Németi (1994) using the methods of algebraic logic.     

粗糙逻辑中理论相容性的拓扑刻画

有关文献将计量化方法应用于粗糙逻辑之中,建立起了用以处理近似推理问题的粗糙逻辑度量空间理论。拟借助于粗糙逻辑度量空间理论,从拓扑学的角度给出粗糙逻辑理论相容性的等价刻画。     

Understanding the role of noise in stochastic local search: Analysis and experiments

Stochastic local search (SLS) algorithms have recently been proven to be among the best approaches to solving computationally hard problems. SLS algorithms typically have a number of parameters, optimized empirically, that characterize and determine their performance. In this article, we focus on the noise parameter. The theoretical foundation of SLS, including an understanding of how to the optimal noise varies with problem difficulty, is lagging compared to the strong empirical results obtained using these algorithms. A purely empirical approach to understanding and optimizing SLS noise, as problem instances vary, can be very computationally intensive. To complement existing experimental results, we formulate and analyze several Markov chain models of SLS in this article. In particular, we compute expected hitting times and show that they are rational functions for individual problem instances as well as their mixtures. Expected hitting time curves are analytical counterparts to noise response curves reported in the experimental literature. Hitting time analysis using polynomials and convex functions is also discussed. In addition, we present examples and experimental results illustrating the impact of varying noise probability on SLS run time. In experiments, where most probable explanations in Bayesian networks are computed, we use synthetic problem instances as well as problem instances from applications. We believe that our results provide an improved theoretical understanding of the role of noise in stochastic local search, thereby providing a foundation for further progress in this area.     

Design and analysis of stochastic local search for the multiobjective traveling salesman problem

Stochastic local search (SLS) algorithms are typically composed of a number of different components, each of which should contribute significantly to the final algorithm's performance. If the goal is to design and engineer effective SLS algorithms, the algorithm developer requires some insight into the importance and the behavior of possible algorithmic components. In this paper, we analyze algorithmic components of SLS algorithms for the multiobjective travelling salesman problem. The analysis is done using a careful experimental design for a generic class of SLS algorithms for multiobjective combinatorial optimization. Based on the insights gained, we engineer SLS algorithms for this problem. Experimental results show that these SLS algorithms, despite their conceptual simplicity, outperform a well-known memetic algorithm for a range of benchmark instances with two and three objectives.     

On the use of design defect examples to detect model refactoring opportunities

Design defects are symptoms of design decay, which can lead to several maintenance problems. To detect these defects, most of existing research is based on the definition of rules that represent a combination of software metrics. These rules are sometimes not enough to detect design defects since it is difficult to find the best threshold values; the rules do not take into consideration the programming context, and it is challenging to find the best combination of metrics. As an alternative, we propose in this paper to identify design defects using a genetic algorithm based on the similarity/distance between the system under study and a set of defect examples without the need to define detection rules. We tested our approach on four open-source systems to identify three potential design defects. The results of our experiments confirm the effectiveness of the proposed approach.     

On Local Stratifiability of Logic Prograns and Databases

In this paper,we deal with the problem of verifying local stratifiability of logic programs and databases presented by Przymusinski.Necessary and sufficient condition for the local stratifiability of logic programs are presented and algorithms of performing the verification are developed.Finally,we prove that a database D B containing clauses with disjunctive consequents can be easily converted into a logic program P such that D B is locally statified iff P is locally stratified.     

Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools

Several grammar-based genetic programming algorithms have been proposed in the literature to automatically generate heuristics for hard optimization problems. These approaches specify the algorithmic building blocks and the way in which they can be combined in a grammar; the best heuristic for the problem being tackled is found by an evolutionary algorithm that searches in the algorithm design space defined by the grammar.In this work, we propose a novel representation of the grammar by a sequence of categorical, integer, and real-valued parameters. We then use a tool for automatic algorithm configuration to search for the best algorithm for the problem at hand. Our experimental evaluation on the one-dimensional bin packing problem and the permutation flowshop problem with weighted tardiness objective shows that the proposed approach produces better algorithms than grammatical evolution, a well-established variant of grammar-based genetic programming. The reasons behind such improvement lie both in the representation proposed and in the method used to search the algorithm design space.     

Exploring the logic of mobile search

After more than a decade of development work and hopes, the usage of mobile Internet has finally taken off. Now, we are witnessing the first signs of evidence of what might become the explosion of mobile content and applications that will be shaping the (mobile) Internet of the future. Similar to the wired Internet, search will become very relevant for the usage of mobile Internet. Current research on mobile search has applied a limited set of methodologies and has also generated a narrow outcome of meaningful results. This article covers new ground, exploring the use and visions of mobile search with a users' interview-based qualitative study. Its main conclusion builds upon the hypothesis that mobile search is sensitive to a mobile logic different than today's one. First, (advanced) users ask for accessing with their mobile devices the entire Internet, rather than subsections of it. Second, success is based on new added-value applications that exploit unique mobile functionalities. The authors interpret that such mobile logic involves fundamentally the use of personalised and context-based services.     

On learning to recognize 3-D objects from examples

Previous results on nonlearnability of visual concepts relied on the assumption that such concepts are represented as sets of pixels. The author uses an approach developed by Haussler (1989) to show that under an alternative, feature-based representation, recognition is probably approximately correct (PAC) learnable from a feasible number of examples in a distribution-free manner     

Application of stochastic control techniques to chaotic nonlinearsystems

A control algorithm based on stochastic control techniques is devised for chaotic nonlinear systems. The algorithm uses a state estimator based on the Kalman filter, and yields performance improvements in at least some regions of state space with respect to that obtainable by use of a controller utilizing only the conditional mean of the system state vector. The method is applied to two typical chaotic nonlinear systems (the Henon-Heiles system and the Lorenz system), and their behavior with control is explored numerically     

On detection of lines using search techniques and list processing

Two-line detection algorithms using best first and depth first search techniques, and another algorithm for line detection by joining the line segments based on the principle of A?, are proposed. The algorithms are suitable to detect lines from low-resolution low-contrast images. Shortcomings of conventional approaches, including tracking, have been discussed, and the power of proposed techniques over tracking is illustrated. Results of proposed algorithms are compared with one another. The advantage of these AI-based techniques is that lines of different confidence value (strength) and with at least a certain length can be detected, hence the effect of noise is greatly reduced.     

AGATHA: Using heuristic search to automate the construction of case law theories

In this paper we describe AGATHA, a program designed to automate the process of theory construction in case based domains. Given a seed case and a number of precedent cases, the program uses a set of argument moves to generate a search space for a dialogue between the parties to the dispute. Each move is associated with a set of theory constructors, and thus each point in the space can be associated with a theory intended to explain the seed case and the other cases in the domain. The space is large and so an heuristic search method is needed. This paper describes two methods based on A* and alpha/beta pruning and also a series of experiments designed to explore the appropriateness of different evaluation functions, the most useful precedents to use as seed cases and the quality of the resulting theories.     

Linking temporal first-order logic with Bayesian networks for the simulation of pervasive computing systems

The authors’ previous work discussed a scalable abstract knowledge representation and reasoning scheme for Pervasive Computing Systems, where both low-level and abstract knowledge is maintained in the form of temporal first-order logic (TFOL) predicates. Furthermore, we introduced a novel concept of a generalised event, an abstract event, which we define as a change in the truth value of an abstract TFOL predicate. Abstract events represent real-time knowledge about the system and they are defined with the help of well-formed TFOL expressions whose leaf nodes are concrete, low-level events using our AESL language.In this paper, we propose to simulate pervasive systems by providing estimated knowledge about its entities and situations that involve them. To achieve this goal, we enhance AESL with higher-order function predicates that denote approximate knowledge about the likelihood of a predicate instance having the value True with respect to a time reference. We define a mapping function between a TFOL predicate and a Bayesian network that calculates likelihood estimates for that predicate as well as a confidence level, i.e., a metric of how reliable the likelihood estimation is for that predicate.Higher-order likelihood predicates are implemented by a novel middleware component, the Likelihood Estimation Service (LES). LES implements the above mapping; first, for each abstract predicate, it learns a Bayesian network that corresponds to that predicate from the knowledge stored in the sensor-driven system. Once trained and validated, the Bayesian networks generate a likelihood estimate and a confidence level. This new knowledge is maintained in the middleware as approximate knowledge therefore providing a simulation of the pervasive system, in the absence of real-time data. Last but not least, we describe an experimental evaluation of our system using the Active BAT location system.     

An intelligent modeling and analysis method of manufacturing process using the first-order predicate logic

Manufacturing process refers to machining sequence from raw materials to final products. Process plan has important effects on manufacturing process. In general, process designer relies on his experience and knowledge to arrange the process plan. For a complex part, it takes long time and effort to determine process plan. In this paper, an intelligent modeling and analysis method using the first-order predicate logic is proposed to evaluate the manufacturing performance. First, the logic predicates used to represent the process plan are defined according to the machining methods, and the predicate variables are discussed in detail. Consequently, the process plan can be represented in the form of the first-order predicate logic. Second, a type of element model composed of four nodes and four links is put forward in order to construct the process model. All components in this element model are respectively explained, and the mapping relationship between element model and predicate logic is described in detail. According to engineering practices, logic inference rules are suggested and the inference process is illustrated. Hence, the manufacturing process model can be constructed. Third, the process simulation is carried out to evaluate the performance of manufacturing system by using measures such as efficiency, the machine utilization, etc. Finally, a case study is given to explain this intelligent modeling method using the first-order predicate logic.     

The use of Remote Sensing techniques and empirical tectonic models for inference of geological structures: Bridging from regional to local scales

Practical and economic constraints prompt the need of obtaining structural geological information with reduced field effort. This paper presents a methodological strategy for deriving such information from remotely sensed (RS) images coupled with empirical tectonic models as a way of bridging from regional to local scales. The hypothesis that spatial organisation displayed by small-scale tectonic structures (and not only the large ones) could be correlated with the arrangement of natural linear features observed on RS imagery to allow inferences on the local geological structure was tested.Azimuth direction and subsidiarily length were found to be the most appropriate attributes for spatial characterisation and comparative analyses of line sets. Inferences made of tectonic structures and respective directional arrangements were based on a combination of qualitative (visual analysis of histograms) and statistical methods (non-parametric goodness-of-fit tests).The numerical evaluation of the results of tests expressed in terms of average degree of matching (91% to 95%) and errors (5% of omission errors and 31.2% of commission errors) showed a reasonable efficiency of the inferential approach in predicting the structural geological settings in lithological units as well as in mid-size areas (50 to 80 km² approximately). Potential applications of the inferential approach in terrain evaluation schemes, particularly for planning and engineering-related purposes, are envisaged.