一个程序验证器的设计和实现

形式验证是提高软件可信程度的重要方法,基于逻辑推理对程序性质进行严格的自动证明是当前的研究热点,但尚无可供工业界使用的产品,其根源在于自动定理证明方面的困难.介绍在通过程序分析建立起各程序点的形状图的基础上,如何利用形状图提供的信息来支持程序验证的方法.提出一种利用形状图信息来消除访问路径别名,使得指针程序中非指针部分的性质仍然可以用Hoare逻辑来进行验证的方法,并证明了该方法的可靠性.还提出一种在不使用自定义谓词的情况下,易变数据结构上数据性质的描述和验证方法.另外,介绍所设计并实现的基于上述方法的PointerC语言的程序验证器的原型.它不仅能自动验证操作易变数据结构程序的性质,也能自动验证使用一维数组的程序的性质.     

断言语言支持自定义谓词的程序验证器原型

基于逻辑推理的方法进行程序验证是形式化程序验证的研究热点.目前的自动验证工具为了保证自动性,对描述程序性质的断言语言都有较多限制,导致程序的某些递归性质难以用断言语言表述.本文在一个面向指针程序、基于先前自行设计的形状图逻辑、依赖于自动定理证明工具Z3的自动程序验证原型系统上,通过在断言语言中引入自定义谓词来增强断言语言的表达能力,使得该原型系统不仅能自动验证含操作易变数据结构的程序的性质,也能自动验证一些不含指针的程序的性质.     

一种用于指针程序的形状分析方法

指针程序的分析一直是研究热点。本文提出一种基于形状图逻辑的形状分析方法,其中形状分析采用形状图来表达程序中指针的指向和相等关系,并用形状图逻辑来进行推理。形状图逻辑是一种把形状图看成有关指针的断言,并在此基础上对Hoare逻辑进行扩展而得到的程序逻辑。首先介绍所提出的形状图和形状图逻辑;然后在此基础之上,设计一种基于形状图逻辑的形状分析方法。     

A Shape Graph Logic and A Shape System

Analysis and verification of pointer programs are still difficult problems so far. This paper uses a shape graph logic and a shape system to solve these problems in two stages. First, shape graphs at every program point are constructed using an analysis tool. Then, they are used to support the verification of other properties （e.g., orderedness）. Our prototype supports automatic verification of programs manipulating complex data structures such as splay trees, treaps, AVL trees and AA trees, etc. The proposed shape graph logic, as an extension to Hoare logic, uses shape graphs directly as assertions. It can be used in the analysis and verification of programs manipulating mutable data structures. The benefit using shape graphs as assertions is that it is convenient for acquiring the relations between pointers in the verification stage. The proposed shape system requires programmers to provide lightweight shape declarations in recursive structure type declarations. It can help rule out programs that construct shapes deviating from what programmers expect （reflected in shape declarations） in the analysis stage. As a benefit, programmers need not provide specifications （e.g., pre-/post-conditions, loop invariants） about pointers. Moreover, we present a method doing verification in the second stage using traditional Hoare logic rules directly by eliminating aliasing with the aid of shape graphs. Thus, verification conditions could be discharged by general theorem provers.     

Deterministic VLSI block placement algorithm using Less Flexibility First principle

In this paper,a simple while effective deterministic algorithm for solving the VLSI block placement problem is proposed considering the packing area and interconnect wiring simultaneously.The algorithm is based on a principle inspired by observations of ancient professionals in solving their similar problems.Using the so-called Less Flexibility First principle,it is tried to pack blocks with the least packing flexibility on its shape and interconnect requirement to the empty space with the least packing flexibility in a greedy manner.Experimental results demonstrate that the algorithm,though simple,is quite effective in solving the problem.The same philosophy could also be used in designing efficient heuristics for other hard problems,such as placement with preplaced modules,placement with L/T shape modules,etc.     

An Efficient Optimization Procedure for Tetrahedral Meshes by Chaos Search Algorithm

A simple and efficient local optimization-based procedure for node reposition-ing/smoothing of three-dimensional tetrahedral meshes is presented.The initial tetrahedral mesh is optimized with respect to a specified element shape measure by chaos search algorithm,which is very effective for the optimization problems with only a few design variables.Examples show that the presented smoothing procedure can provide favorable conditions for local transformation approach and the quality of mesh can be significantly improved by the combination of these two procedures with respect to a specified element shape measure.Meanwhile,several commonly used shape measures for tetrahedral element,which are considered to be equivalent in some weak sense over a long period of time,are briefly re-examined in this paper.Preliminary study indicates that using different measures to evaluate the change of element shape will probably lead to inconsistent result for both well shaped and poorly shaped elements.The proposed smoothing approach can be utilized as an appropriate and effective tool for evaluating element shape measures and their influence on mesh optimization process and optimal solution.     

一种汇编程序的形式验证框架

在高可信软件的各种性质中,安全性是关注的重点.软件满足安全策略的证明方法是安全性研究的热点之一.根据前期提出的安全程序设计与证明的框架以及指针逻辑推理系统,介绍在所实现的出具证明编译器(certifying compiler)原型系统中有关目标机器的形式定义、汇编程序的形式验证框架以及汇编程序指针程序性质证明等方面的研究.它们的主要特点是汇编验证框架是基于Hoare风格的程序验证方式;与指针有关的性质使用和源语言一级类似的指针逻辑推理系统进行证明;使用一个简单的类型系统完成有关指针的类型检查.     

Two kinds of optimal controls for probabilistic mix-valued logical dynamic networks

This paper addresses two kinds of optimal control problems of probabilistic mix-valued logical control networks by using the semi-tensor product of matrices, and presents a number of new results on the optimal finite-horizon control and the first-passage model based control problems, respectively. Firstly, the probabilistic mix-valued logical control network is expressed in an algebraic form by the semi-tensor product method, based on which the optimal finite-horizon control problem is studied and a new algorithm for choosing a sequence of control actions is established to minimize a given cost functional over finite steps. Secondly, the first-passage model of probabilistic mix-valued logical networks is given and a new algorithm for designing the optimal control scheme is proposed to maximize the corresponding probability criterion. FinMly, an illustrative example is studied to support our new results/algorithms.     

Distance-Based Classifier via the Kernel Trick

For classifying large data sets, we propose a discriminant kernel that introduces a nonlinear mapping from the joint space of input data and output label to a discriminant space. Our method differs from traditional ones, which correspond to map nonlinearly from the input space to a feature space. The induced distance of our discriminant kernel is Eu- clidean and Fisher separable, as it is defined based on distance vectors of the feature space to distance vectors on the discriminant space. Unlike the support vector machines or the kernel Fisher discriminant analysis, the classifier does not need to solve a quadric program- ming problem or eigen-decomposition problems. Therefore, it is especially appropriate to the problems of processing large data sets. The classifier can be applied to face recognition, shape comparison and image classification benchmark data sets. The method is significantly faster than other methods and yet it can deliver comparable classification accuracy.     

More Proofs of an Axiom of Łukasiewicz

This paper reports results and some new problems in one of the domains to which automatic first-order theorem provers have been most successfully applied: axiomatics of nonclassical propositional logics. It is well known that one of the standard axioms of the denumerable-valued pure implication logic of ukasiewicz becomes derivable from the remainder in the presence of negation. Here it is shown that the same axiom is similarly derivable using conjunction and disjunction instead of negation. This closes a problem left open by Harris and Fitelson (Journal of Automated Reasoning 27, 2001). Related problems are discussed, and five such open problems are proposed as challenges to the automated reasoning community.     

Logic as an integrated modeling framework

There is a growing interest in the application of Artificial Intelligence (AI) tools and techniques to management science problems. A rich variety of commercial AI software products is now emerging to facilitate this. However, there has been little integration between AI and Management Science (MS) at a theoretical level. This paper proposes the use of formal logic as the basis for this conceptual bridge, and the use of logic programming as a modeling language for management science applications. The framework is illustrated by a logic-based representation, called PM, for specifying production, distribution and inventory problems.     

基于泛逻辑学的柔性命题逻辑研究

现有的数理逻辑是刚性逻辑，不能满足研究不确定性问题的需要．概率测度是研究不确定性问题的重要数学工具．但作为概率推理理论基础的概率逻辑发展不够成熟，影响了它在不确定性推理中的广泛应用．本文第二作者在探索包含确定性和各种不确定性的现实世界逻辑规律的基础上．建立一个包容刚性逻辑和柔性逻辑的命题泛逻辑学体系．本文利用这一研究成果，对命题概率逻辑进行了探讨．     

动态模糊逻辑(DFL)程序设计语言的结构化操作语义

动态模糊问题在客观世界中是普遍存在的,作为解决动态模糊问题的理论工具-动态模糊逻辑(DFL)已有十年的研究历史了,为了更有效地解决动态模糊问题,使DFL成为一种切实可实现的逻辑系统,有必要研究设计一种适合解决动态模糊性问题的程序设计语言.仿照监督命令的程序结构,给出动态模糊程序设计语言的结构化操作语义,其内容包括:动态模糊逻辑程序设计语言的抽象语法、动态模糊语义并通过一个简单实例说明其有效性.     

Constraint Lingo: towards high‐level constraint programming

Logic programming requires that the programmer convert a problem into a set of constraints based on predicates. Choosing the predicates and introducing appropriate constraints can be intricate and error prone. If the problem domain is structured enough, we can let the programmer express the problem in terms of more abstract, higher‐level constraints. A compiler can then convert the higher‐level program into a logic‐programming formalism. The compiler writer can experiment with alternative low‐level representations of the higher‐level constraints in order to achieve a high‐quality translation. The programmer can then take advantage of both a reduction in complexity and an improvement in runtime speed for all problems within the domain. We apply this analysis to the domain of tabular constraint‐satisfaction problems. Examples of such problems include logic puzzles solvable on a hatch grid and combinatorial problems such as graph coloring and independent sets. The proper abstractions for these problems are rows, columns, entries, and their interactions. We present a higher‐level language, Constraint Lingo, dedicated to problems in this domain. We also describe how we translate programs from Constraint Lingo into lower‐level logic formalisms such as the logic of propositional schemata. These translations require that we choose among competing lower‐level representations in order to produce efficient results. The overall effectiveness of our approach depends on the appropriateness of Constraint Lingo, our ability to translate Constraint Lingo programs into high‐quality representations in logic formalisms, and the efficiency with which logic engines can compute answer sets. We comment on our computational experience with these tools in solving both graph problems and logic puzzles. Copyright © 2004 John Wiley & Sons, Ltd.     

由一阶逻辑公式得到命题逻辑可满足性问题实例

命题逻辑可满足性(SAT)问题是计算机科学中的一个重要问题.近年来许多学者在这方面进行了大量的研究,提出了不少有效的算法.但是,很多实际问题如果用一组一阶逻辑公式来描述,往往更为自然.当解释的论域是一个固定大小的有限集合时,一阶逻辑公式的可满足性问题可以等价地归约为SAT问题.为了利用现有的高效SAT工具,提出了一种从一阶逻辑公式生成SAT问题实例的算法,并描述了一个自动的转换工具,给出了相应的实验结果.还讨论了通过增加公式来消除同构从而减小搜索空间的一些方法.实验表明,这一算法是有效的,可以用来解决数学研究和实际应用中的许多问题.     

Prioritized conditional imperatives: problems and a new proposal

The sentences of deontic logic may be understood as describing what an agent ought to do when faced with a given set of norms. If these norms come into conflict, the best the agent can be expected to do is to follow a maximal subset of the norms. Intuitively, a priority ordering of the norms can be helpful in determining the relevant sets and resolve conflicts, but a formal resolution mechanism has been difficult to provide. In particular, reasoning about prioritized conditional imperatives is overshadowed by problems such as the ‘order puzzle’ that are not satisfactorily resolved by existing approaches. The paper provides a new proposal as to how these problems may be overcome.     

热电厂锅炉灭火保护系统的改造

对灭火保护系统的诸多问题进行分析，并解决了冗余配置的问题。