Adhesive DPO Parallelism for Monic Matches

This paper presents indispensable technical results of a general theory that will allow to systematically derive from a given reduction system a behavioral congruence that respects concurrency. The theory is developed in the setting of adhesive categories and is based on the work by Ehrig and König on borrowed contexts; the latter are an instance of relative pushouts, which have been proposed by Leifer and Milner. In order to lift the concurrency theory of dpo rewriting to borrowed contexts we will study the special case of dpo rewriting with monic matches in adhesive categories: more specifically we provide a generalized Butterfly Lemma together with a Local Church Rosser and Parallelism theorem.     

Predicting Incompatibility of Transformations in Model-driven Development

The grand vision of model-driven development and model-driven architecture (MDA) is to generate automatically an implementation from a high-level model of the application. The primary ingredients of model-driven development are a platform-independent model (PIM) of the application and a platform-specific model (PSM) which is derived from the PIM for a given target platform. The transformation from PIM to PSM could be done automatically if necessary mappings are defined. Even if this grand vision were to be realized sometime in the future, the evolution of applications developed in this way still poses interesting challenges. We point out specific problems that arise when evolving an application to support different platforms and different technologies. We then propose a supporting tool called a "portability checker" that can help the application developer in evolving applications developed using MDA.     

分布式系统上异步算法的终止

本文论述了一种检测分布式系统上异步算法终止的有效方法．     

Leveraging UML Profiles to Generate Plugins From Visual Model Transformations

Model transformation is a fundamental technology in the MDA. Therefore, model transformations should be treated as first class entities, that is, models. One could use the metamodel of SDM, a graph based object transformation language, as the metamodel of such transformation models. However, there are two problems associated with this. First, SDM has a non-standardized metamodel, meaning a specific tool (Fujaba) would be needed to write transformation specifications. Secondly, due to assumptions of the code generator, the transformations could only be deployed on the Fujaba tool itself. In this paper, we describe how these issues have been overcome through the development of a template based code generator that translates instances of a UML profile for SDM to complete model transformation code that complies to the JMI standard. We have validated this approach by specifying a simple visual refactoring in one UML tool and deploying the generated plugin on another UML tool.     

Criteria for driver impairment

Most traffic accidents can be attributed to driver impairment, e.g. inattention, fatigue, intoxication, etc. It is now technically feasible to monitor and diagnose driver behaviour with respect to impairment with the aid of a limited number of in-vehicle sensors. However, a valid framework for the evaluation of driver impairment is still lacking. To provide an acceptable definition of driver impairment, a method to assess absolute and relative criteria was proposed to fulfil the paradoxical goal of defining impaired driving which is consistent yet adaptable to interindividual differences.     

Matrix Interpretations for Proving Termination of Term Rewriting

We present a new method for automatically proving termination of term rewriting. It is based on the well-known idea of interpretation of terms where every rewrite step causes a decrease, but instead of the usual natural numbers we use vectors of natural numbers, ordered by a particular nontotal well-founded ordering. Function symbols are interpreted by linear mappings represented by matrices. This method allows us to prove termination and relative termination. A modification of the latter, in which strict steps are only allowed at the top, turns out to be helpful in combination with the dependency pair transformation. By bounding the dimension and the matrix coefficients, the search problem becomes finite. Our implementation transforms it to a Boolean satisfiability problem (SAT), to be solved by a state-of-the-art SAT solver.     

Abstract Graph Transformation

Graphs may be used as representations of system states in operational semantics and model checking; in the latter context, they are being investigated as an alternative to bit vectors. The corresponding transitions are obtained as derivations from graph production rules.In this paper we propose an abstraction technique in this framework: the state graphs are contracted by collecting nodes that are sufficiently similar (resulting in smaller states and a finite state space) and the application of the graph production rules is lifted to this abstract level. Since graph abstractions and rule applications can all be computed completely automatically, we believe that this can be the core of a practically feasible technique for software model checking.     

Termination of linear programs with nonlinear constraints

Tiwari (2004) proved that the termination problem of a class of linear programs (loops with linear loop conditions and updates) over the reals is decidable through Jordan forms and eigenvector computation. Braverman (2006) proved that it is also decidable over the integers. Following their work, we consider the termination problems of three more general classes of programs which are loops with linear updates and three kinds of polynomial loop conditions, i.e., strict constraints, non-strict constraints and both strict and non-strict constraints, respectively. First, we prove that the termination problems of such loops over the integers are all undecidable. Then, for each class we provide an algorithm to decide the termination of such programs over the reals. The algorithms are complete for those programs satisfying a property, Non-Zero Minimum.     

Termination of High-Level Replacement Units with Application to Model Transformation

Visual rewriting techniques, in particular graph transformations, are increasingly used to model transformations of systems specified through diagrammatic sentences. Several rewriting models have been proposed, differing in the expressivity of the types of rules and in the complexity of the rewriting mechanism; yet basic results concerning the formal properties of these models are still missing for many of them. In this paper, we propose a contribution towards solving the termination problem for rewriting systems with external control mechanisms. In particular, we obtain results of more general validity by extending the concept of transformation unit to high-level replacement systems, a generalization of graph transformation systems. For high-level replacement units, we state and prove several abstract properties based on termination criteria. Then, we instantiate the high-level replacement systems by attributed graph transformation systems and present concrete termination criteria. These are used to show the termination of some replacement units needed to express model transformations as a consequence of software refactoring.     

The design of a language for model transformations

Model-driven development of software systems envisions transformations applied in various stages of the development process. Similarly, the use of domain-specific languages also necessitates transformations that map domain-specific constructs into the constructs of an underlying programming language. Thus, in these cases, the writing of transformation tools becomes a first-class activity of the software engineer. This paper introduces a language that was designed to support implementing highly efficient transformation programs that perform model-to-model or model-to-code translations. The language uses the concepts of graph transformations and metamodeling, and is supported by a suite of tools that allow the rapid prototyping and realization of transformation tools.     

两类量子游走组成的非确定型量子程序的终止验证

首先给出了C4空间中由量子游走组成的非确定型量子程序的概念,其次讨论了它们从初态运行时在不同的测量算子下的可达集合、终止集合和发散集合。研究表明:非确定型量子程序的终止、发散和可达集合、发散集合与选取的测量算子有密切的关系。程序在不同测量算子作用下从同一个初态运行时可能终止,也可能发散;并且,同一个初态的可达集合中终态和发散态共存。     

Combining overlap and containment for gene assembly in ciliates

Gene assembly in ciliates is an intricate biological process that has been studied formally and modeled through string and graph rewriting systems. Recently, a restriction of the general (intramolecular) model, called simple gene assembly, has been introduced. This restriction has subsequently been defined as a string rewriting system. We show that, by extending the notion of overlap graph to also represent containment, it is possible to define an equivalent graph rewriting system for two of the three types of rules that make up simple gene assembly. It turns out that this graph rewriting system is often less involved to study than its corresponding string rewriting system. We illustrate this by giving characterizations of the ‘power’ of both types of graph rewriting rules. Also, a first step is made towards a characterization of the “extended overlap graphs”.     

Termination Criteria for Bounded Model Checking: Extensions and Comparison

Increasing attention has been paid recently to criteria that allow one to conclude that a structure models a linear-time property from the knowledge that no counterexamples exist up to a certain length. These termination criteria effectively turn Bounded Model Checking into a full-fledged verification technique and sometimes result in considerable time savings. In [M. Awedh and F. Somenzi. Proving more properties with bounded model checking. In R. Alur and D. Peled, editors, Sixteenth Conference on Computer Aided Verification (CAV'04), pages 96–108. Springer-Verlag, Berlin, July 2004. LNCS 3114] we presented a criterion based on the translation of the linear-time specification into a Büchi automaton. BMC can be terminated if no fair cycle is found up to a given length, and one can prove that no fair cycle exists beyond that length. The maximum length for which counterexamples are explicitly checked is called the termination length; it obviously depends on the model, the property, and the termination criterion. In this paper we improve the criterion of [M. Awedh and F. Somenzi. Proving more properties with bounded model checking. In R. Alur and D. Peled, editors, Sixteenth Conference on Computer Aided Verification (CAV'04), pages 96–108. Springer-Verlag, Berlin, July 2004. LNCS 3114] by adding a check that often substantially reduces termination length. Our previous work employed translation to a non-generalized Büchi automaton. Though a well-known technique converts a generalized automaton into that form by composing it with a counter, it has the undesirable effect of considerably lengthening the cycles in the graph to be searched. We propose several alternatives to that approach and compare them experimentally. The translation to automata can be accomplished in more than one way, and in this paper we contrast two of them: one based on the algorithms of [F. Somenzi and R. Bloem. Efficient Büchi automata from LTL formulae. In E. A. Emerson and A. P. Sistla, editors, Twelfth Conference on Computer Aided Verification (CAV'00), pages 248–263. Springer-Verlag, Berlin, July 2000. LNCS 1855], and one based on the notion of tight automaton of [E. Clarke, O. Grumberg, and K. Hamaguchi. Another look at LTL model checking. In D. L. Dill, editor, Sixth Conference on Computer Aided Verification (CAV'94), pages 415–427. Springer-Verlag, Berlin, 1994. LNCS 818]. The latter yields shorter counterexamples, but the former often leads to earlier termination. In addition, it can help in identifying safety properties, for which termination checks are much more efficient than for the general case. We finally present results on comparing techniques based on cycle detection to the technique of [V. Schuppan and A. Biere. Efficient reduction of finite state model checking to reachability analysis. Software Tools for Technology Transfer, 5(2–3):185–204, Mar. 2004], which converts liveness properties into safety properties by augmentation of the model.     

Refinement Patterns for UML

This paper describes strategies or 'patterns' for the refinement of UML specifications into executable implementations, using a semantically precise subset, UML-RSDS, of UML.     

基于抽象解释的服务间消息的数据约减

面向服务软件中服务间消息的变量值可能存在无穷域的情况,从而导致模型检测时产生状态空间爆炸问题。为了使终止性验证在实践上可行,需要约减模型状态空间的大小,使得计算时间和空间需求合理。为此,基于抽象解释的区间抽象理论扩展了经典区间抽象域方法,并在统一的区间抽象域方法上借助异常控制流图对变量进行区间分析,在此基础上逆向分析得到服务间消息的变量区间集。变量区间上任意值相对于终止性验证是等价性,因此从每一个变量区间集中选取一个代表值,可组成服务间消息变量的约减值,从而为异常处理的终止性验证提供了约减的初始配置,有效避免了状态空间爆炸。     

实现稳定双向认知映射的逆向云变换算法

人类对客观世界认知的不确定性主要通过认知的最小(基本)单元——概念反映出来。本文基于云模型理论,提出一种新的稳定逆向云变换算法,通过实验对比分析说明该方法的稳定性;再根据正向云变换由概念内涵生成概念外延及逆向云变换由概念外延形成概念内涵的特点,利用正向云变换算法和逆向云变换算法模拟人们对概念的稳定双向认知计算过程,即概念内涵与外延之间的稳定双向认知计算过程。     

一种基于J2EE平台的MDA模型转换技术*

为了解决不同中间件平台的应用集成和互操作, OMG 提出了MDA 的概念。MDA 的一个重要思想就是将系统模型划分成与平台无关的模型( PIM) 和与平台有关的模型( PSM) , 并建立这两种模型之间的映射关系。给出了一个属于PIM 的Domain Model 和一个属于PSM 的Application Model, 并基于J2EE 架构描述了Do-main Model 到Application Model 的转换方法。     

基于凸面单形体的Vague集向Fuzzy集转化模型

利用Vague集与凸面单形体同一平面内3个三角形的对应关系,给出一种Vague集及其向Fuzzy集转化的单形体几何表示方法,有效解决Vague集向Fuzzy集转化方法或模型中的几何解释问题。提出Vague集向Fuzzy集转化的单形体转化模型(S-TM),以及应满足的转化准则。与已有转化方法或模型相比,S-TM具有更直观的几何表示和更明确、更确定的几何解释,是一种更为有效的转化模型,并说明Vague集向Fuzzy集的转化具有模糊性和逐渐转化性。