Parallel Assignments in Software Model Checking

In this paper we investigate how formal software verification systems can be improved by utilising parallel assignment in weakest precondition computations.We begin with an introduction to modern software verification systems. Specifically, we review the method in which software abstractions are built using counterexample-guided abstraction refinement (CEGAR). The classical NP-complete parallel assignment problem is first posed, and then an additional restriction is added to create a special case in which the problem is tractable with an O(n²) algorithm. The parallel assignment problem is then discussed in the context of weakest precondition computations. In this special situation where statements can be assumed to execute truly concurrently, we show that any sequence of simple assignment statements without function calls can be transformed into an equivalent parallel assignment block.Results of compressing assignment statements into a parallel form with this algorithm are presented for a wide variety of software applications. The proposed algorithms were implemented in the ComFoRT reasoning framework [J. Ivers and N. Sharygina. Overview of ComFoRT: A model checking reasoning framework. Technical Report CMU/SEI-2004-TN-018, Carnegie Mellon Software Engineering Institute, 2004] and used to measure the improvement in the verification of real software systems. This improvement in time proved to be significant for many classes of software.     

核电厂用水合理性分析及体会

岭澳核电站三期扩建工程属滨海核电工程。滨海地区一般水资源相对紧缺,而且我国尚未制定核电行业的用水定额标准,因此,如何合理地评价核电工程的设计用水水平是核电水资源论证的重点和难点。根据核电施工期较长的特点及项目工期安排,分施工期、调试期、正常运行期及可能组合,论证了项目用水的合理性,并对已建成的核电站的历史用水量进行了调查研究,分析了项目的节水潜力,提出了合理的取用水量,可为核电厂水资源论证提供参考。     

Visual abstraction of dynamic network via improved multi-class blue noise sampling

Massive sequence view (MSV) is a classic timeline-based dynamic network visualization approach. However, it is vulnerable to visual clutter caused by overlapping edges, thereby leading to unexpected misunderstanding of time-varying trends of network communications. This study presents a new edge sampling algorithm called edge-based multi-class blue noise (E-MCBN) to reduce visual clutter in MSV. Our main idea is inspired by the multi-class blue noise (MCBN) sampling algorithm, commonly used in multi-class scatterplot decluttering. First, we take a node pair as an edge class, which can be regarded as an analogy to classes in multi-class scatterplots. Second, we propose two indicators, namely, class overlap and inter-class conflict degrees, to measure the overlapping degree and mutual exclusion, respectively, between edge classes. These indicators help construct the foundation of migrating the MCBN sampling from multi-class scatterplots to dynamic network samplings. Finally, we propose three strategies to accelerate MCBN sampling and a partitioning strategy to preserve local high-density edges in the MSV. The result shows that our approach can effectively reduce visual clutters and improve the readability of MSV. Moreover, our approach can also overcome the disadvantages of the MCBN sampling (i.e., long-running and failure to preserve local high-density communication areas in MSV). This study is the first that introduces MCBN sampling into a dynamic network sampling.     

Knowledge-based spatiotemporal linear abstraction

We present a theoretical framework and a case study for reusing the same conceptual and computational methodology for both temporal abstraction and linear (unidimensional) space abstraction, in a domain (evaluation of traffic-control actions) significantly different from the one (clinical medicine) in which the method was originally used. The method, known asknowledge-based temporal abstraction, abstracts high-level concepts and patterns from time-stamped raw data using a formal theory of domain-specific temporal-abstraction knowledge. We applied this method, originally used to interpret time-oriented clinical data, to the domain of traffic control, in which the monitoring task requires linear pattern matching along both space and time. First we reused the method for creation of unidimensional spatial abstractions over highways, given sensor measurements along each highway measured at the same time point. Second, we reused the method to create temporal abstractions of the traffic behaviour, for the same space segments, but during consecutive time points. We defined the corresponding temporal-abstraction and spatial-abstraction domain-specific knowledge. Our results suggest that (1) the knowledge-base temporal-abstraction method is reusable over time and unidimensional space as well as over significantly different domains; (2) the method can be generalised into a knowledge-based linear-abstraction method, which solves tasks requiring abstraction of data along any linear distance measure; and (3) a spatiotemporal-abstraction method can be assembled, from two copies of the generalised method and a spatial-decomposition mechanism, and is applicable to tasks requiring abstraction of time-oriented data into meaningful spatiotemporal patterns over a linear, decomposable space, such as traffic over a set of highways.     

Integrating a Decision Tree Perspective at the Operational-Level of BPM+

Decision trees are among the best-known decision-making techniques and have been used extensively for both data analysis and predictive modeling. BPM+ is a novel process modeling approach that helps represent business process models in a consistent and structured way to meet different stakeholders’ process representation needs. This paper reports on the outcomes of an ontological analysis of the potential use of decision-tree representations as a new BPM+ perspective for the operational level of abstraction. This new perspective effectively demonstrates how a specialized/operational BPM stakeholder perspective can be used to improve the existing organizational business process model repository.     

Abstractions for DNA circuit design

DNA strand displacement techniques have been used to implement a broad range of information processing devices, from logic gates, to chemical reaction networks, to architectures for universal computation. Strand displacement techniques enable computational devices to be implemented in DNA without the need for additional components, allowing computation to be programmed solely in terms of nucleotide sequences. A major challenge in the design of strand displacement devices has been to enable rapid analysis of high-level designs while also supporting detailed simulations that include known forms of interference. Another challenge has been to design devices capable of sustaining precise reaction kinetics over long periods, without relying on complex experimental equipment to continually replenish depleted species over time. In this paper, we present a programming language for designing DNA strand displacement devices, which supports progressively increasing levels of molecular detail. The language allows device designs to be programmed using a common syntax and then analysed at varying levels of detail, with or without interference, without needing to modify the program. This allows a trade-off to be made between the level of molecular detail and the computational cost of analysis. We use the language to design a buffered architecture for DNA devices, capable of maintaining precise reaction kinetics for a potentially unbounded period. We test the effectiveness of buffered gates to support long-running computation by designing a DNA strand displacement system capable of sustained oscillations.     

Feature-based non-manifold modeling system to integrate design and analysis of injection molding products

Current CAE systems used for both the simulation of the injection molding process and the structural analysis of plastic parts accept solid models as geometric input. However, abstract models composed of sheets and wireframes are still used by CAE systems to carry out more analyses more efficiently. Therefore, to obtain an adequate abstract model, designers often have to simplify and idealize a detailed model of a part to a specific level of detail and/or abstraction. For such a process, we developed a feature-based design system based on a non-manifold modeling kernel supporting feature-based multi-resolution and multi-abstraction modeling capabilities. In this system, the geometric models for the CAD and CAE systems are merged into a single master model in a non-manifold topological representation, and then, for a given level of detail and abstraction, a simplified solid or non-manifold model is extracted immediately for an analysis. For a design change, the design and analysis models are modified simultaneously. As a result, this feature-based design system is able to provide a more integrated environment for the design and analysis of plastic injection molding parts. This paper was recommended for publication in revised form by Associate Editor Tae Hee Lee Sang Hun Lee received his B.S., M.S., and Ph. D. degrees in Mechanical Design and Production Engineering from Seoul National University, Korea, in 1986, 1988, and 1993, respectively. Dr. Lee is currently a Professor at the School of Mechanical and Automotive Engineering at Kookmin University in Seoul, Korea. His research interests include CAD/ CAM, human-centered design and engineering, digital human modeling and simulation, computer-aided automotive design and manufacturing., and computer-aided tooling design.     

An approach to the implementation and verification of abstract data

Abstract

The concept of abstraction can be used to simplify and formalize the design of software. However, most of the existing techniques based on abstraction only consider the control structure but not the data structures in the software. The transformation of a data abstraction, i.e., an abstract data type, to a physical data structure is a complicated process. It is composed of three major parts: a specification technique for describing a data abstraction; a deriving process for deriving the representation of the abstraction based on the specification; and a verification method for verifying the correctness of the specification and the representation of the abstraction. In this paper, we will concentrate on the last two problems, and it is assumed that the algebraic specification technique is used for describing abstract data types. Also, we will use examples to illustrate the use of the proposed approach.     

Revisiting timing in process algebra

We shortly review the framework of process algebras with timing presented by Baeten and Middelburg [Handbook of Process Algebra, Elsevier, 2001, Chapter 10]. In order to cover processes that are capable of performing certain actions at all points in some time interval, we add integration to the process algebra with continuous relative timing from this framework. This extension happens to reveal some points that are peculiar to relative timing. We go into these points. The most flagrant point is that, unlike in case of absolute timing, discretization cannot be added to the extension without first adding a mechanism for parametric timing like initial abstraction.     

基于形态学变权神经网络的数据精炼

本文研究了模式样本的选取操作要领和典型样本数据的精炼方法.为改善神经网络普遍存在着误差精度与收敛速率对初始权值颇为敏感甚至过于依赖的缺陷,采用感受野的Gabor函数模型来优化网络权值的初始量.这不仅能为学习过程提供一个良好的开端,重要的是将赋予网络模型以具备可塑性优化的基础和适应环境变化的潜力.算法运用主成份数学分析法对结构元分量的贡献率进行了统计度量与计算,以提取出对滤波运算最具影响力的主要分量,从而可显著降低数据处理量,使运行速度和学习效率更高.