Multiway Decision Graphs for Automated Hardware Verification

Traditional ROBDD-based methods of automated verification suffer from the drawback that they require a binary representation of the circuit. To overcome this limitation we propose a broader class of decision graphs, called Multiway Decision Graphs (MDGs), of which ROBDDs are a special case. With MDGs, a data value is represented by a single variable of abstract type, rather than by 32 or 64 boolean variables, and a data operation is represented by an uninterpreted function symbol. MDGs are thus much more compact than ROBDDs, and this greatly increases the range of circuits that can be verified. We give algorithms for MDG manipulation, and for implicit state enumeration using MDGs. We have implemented an MDG package and provide experimental results.     

Performance Analysis and Functional Verification of the Stop-and-Wait Protocol in HOL

Real-time systems usually involve a subtle interaction of a number of distributed components and have a high degree of parallelism, which makes their performance analysis quite complex. Thus, traditional techniques, such as simulation, or the state-based formal methods usually fail to produce reasonable results. In this paper, we propose to use higher-order-logic (HOL) theorem proving for the performance analysis of real-time systems. The idea is to formalize the real-time system as a logical conjunction of HOL predicates, whereas each one of these predicates define an autonomous component or process of the given real-time system. The random or unpredictable behavior found in these components is modeled as random variables. This formal specification can then be used in a HOL theorem prover to reason about both functional and performance related properties of the given real-time system. In order to illustrate the practical effectiveness of our approach, we present the analysis of the Stop-and-Wait protocol, which is a classical example of real-time systems. The functional correctness of the protocol is verified by proving that the protocol ensures reliable data transfers. Whereas, the average message delay relation is verified in HOL for the sake of performance analysis. The paper includes the protocol’s formalization details along with the HOL proof sketches for the major theorems.     

A Skeptic's Approach to Combining HOL and Maple

We contrast theorem provers and computer algebra systems, pointing out the advantages and disadvantages of each, and suggest a simple way to achieve a synthesis of some of the best features of both. Our method is based on the systematic separation of search for a solution and checking the solution, using a physical connection between systems. We describe the separation of proof search and checking in some detail, relating it to proof planning and to the complexity class NP, and discuss different ways of exploiting a physical link between systems. Finally, the method is illustrated by some concrete examples of computer algebra results proved formally in the HOL theorem prover with the aid of Maple.     

An Automata-Theoretic Approach to the Reachability Analysis of RPPS Systems

We show how the tree-automata techniques proposed by Lugiez and Schnoebelen apply to the reachability analysis of RPPS systems. Using these techniques requires that we express the states of RPPS systems in a tailor-made process rewrite system where reachability is a relation recognizable by finite tree-automata.     

考虑关联性与优先关系的区间犹豫模糊图决策

区间犹豫模糊集是区间数和犹豫模糊集的推广,通常用以描述不确定信息具备的不完备性与犹豫性.近年来,区间犹豫模糊多属性决策问题受到了学者们的广泛关注.针对属性间同时具有关联性与优先关系的区间犹豫模糊多属性决策问题,利用模糊图可通过顶点间的边表示属性间关联性的优势,研究基于区间犹豫模糊图的多属性决策方法.首先从定义、运算规则及映射关系的角度建立区间犹豫模糊图的相关概念.在此基础上,提出考虑关联性与优先关系的区间犹豫模糊图多属性决策方法.最后用实例及对比性分析阐述所提多属性决策方法的可行性与有效性.结果表明:相较于经典区间犹豫模糊多属性决策方法,所提方法能够合理求解属性间同时具有关联性与优先关系的区间犹豫模糊多属性决策问题.     

Verification of Similar FSMs by Mixing Incremental Re-encoding, Reachability Analysis, and Combinational Checks

State space exploration is often used to prove properties about sequential behavior of Finite State Machines (FSMs). For example, equivalence of two machines is proved by analyzing the reachable state set of their product machine. Nevertheless, reachability analysis is infeasible on large practical examples. Combinational verification is far less expensive, but on the other hand its application is limited to combinational circuits, or particular design schemes. Finally, approximate techniques imply sufficient, not strictly necessary conditions.The purpose of this paper is to extend the applicability of purely combinational checks. This is generally achieved through state minimization, partitioning, and re-encoding the FSMs to factor out their differences. We focus on re-encoding. In particular, we present an incremental approach to re-encoding for verification that transforms the product machine traversal into a combinational verification in the best case, and into a computationally simpler product machine traversal in the general case.Experimental results demonstrate the effectiveness of this technique on medium-large circuits where other techniques may fail.     

一种融合区域生长与图论的图像分割方法

该文提出一种融合区域生长与图论的图像分割方法,一般的基于区域的分割方法在区域生长完成之后需要进行区域的合并,以消除过分割现象。该文的方法在区域生长完成之后,用NormalizedCut方法在区域之间进行分割,产生最终所分割的图像。在方法上区域生长方法考虑的是图像的局部信息,NormalizedCut方法考虑的是图像的全局信息,该文的方法融合了两者的优点。该文的算法主要以灰度图像为研究对象,实验结果表明可以取得很好的分割效果。     

基于活化路径和条件公式的主动规则集可终止性判定方法

支持主动规则机制已经成为现代数据库系统的一个重要特征.主动规则集的可终止性判定是主动数据库中一个核心问题之一,利用触发图和活化图的方法来判定可终止性都存在不同的保守性.为此,提出了为有效活化路径建立条件公式的思想,在此基础上给出了一个新的判定主动规则集可终止性的方法.分析的结果表明,提出的方法较现有方法可以发现更多的可终止性情形,最后给出了相应的算法及其可终止性、正确性证明.