Refinement of Actions in a Real-Time Process Algebra with a True Concurrency Model

In this paper, we develop techniques of action refinement in a real-time process algebra that allows urgent interactions to model timeout. Semantic counterpart is carried out in a real-time non-interleaving causality based setting, timed bundle event structures. We show that our refinement notions have the following nice properties: the observable behaviour of the refined system can be inferred compositionally from the observable behaviour of the original system and from the observable behaviour of the processes substituted for the actions; the timed extensions of observational pomset trace equivalence and observational history preserving bisimulation equivalence are both congruences under our refinement; and the syntactic and semantic refinements coincide up to the aforementioned equivalence relations with respect to a cpo-based denotational semantics.     

Action Refinement Applied to Late Decisions

In modular approaches to specify concurrent systems a system is built up from components using various operators as e.g. the sequential, the parallel, or the choice (+) operator. Usually the choice between two components, i.e. P₁ + P₂, is taken in favor of that component that is first to start an action. We follow here the alternative view that a choice is taken in favor of that component that is the first to terminate an action (end-based choice). This alternative has various applications and interesting implications. In particular the different points of view lead to different action refinement operators. The contribution of this paper is to present here an action refinement operator for the end-based view in a suitable true concurrency setting and to establish two equivalences that are the coarsest congruences for this refinement operator with respect to trace (respectively bisimulation) equivalence. Received July 2003 Revised November 2005 Accepted December 2005 by E. Astesiano     

Compositional Action System Refinement

We show how a parallel composition of action systems can be refined by refining the components separately, and checking non-interference against invariants and guarantee conditions, which are abstract and stable. The guarantee condition can be thought of as a very abstract specification of how a system affects the global state, and it allows us to show that an action system refinement is valid in a given environment, even if we do not know any of the details of that environment. The paper extends the traditional notion of action systems slightly, and it makes use of a generalisation of the attribute model for program variables.     

有限布尔代数上的自动机

本文对有限布尔代数上的自动机进行了研究，证明了有限布尔代数上的可逆内动机保持正交性；定出了有限布尔代数上的对称可逆内动机及一般ｎ（≤３）阶可逆内动机的图型。     

Comparing Syntactic and Semantic Action Refinement

The semantic definition of action refinement on labelled configuration structures is compared with the notion ofsyntactic substitution, which can be used as another notion of action refinement in a process algebraic setting. The comparison is done by studying a process algebra equipped with sequential composition, parallel composition with an explicit synchronisation set, and an operator for action refinement. On the one hand, the language (including the refinement operator) is given a configuration structure semantics. On the other hand, a reduction procedure transforms a process termPinto aflatterm (i.e., with the refinement operator not occurring in it)red(P) by means of syntactic substitution, defined in a structural inductive way. The main aim of the paper is to investigate general conditions under which the termsPandred(P) have the same semantics. The results we present are essentially dependent on the question whether the refined action can be synchronised or not. In the latter case,Pandred(P) give rise to isomorphic configuration structures under mild assumptions. The former case is considerably more difficult, since then refinement cannot be expected to distribute over parallel composition. We give necessary and sufficientsemanticconditions under which distribution still holds up to semantic equivalence. Subsequently, we also give sufficient (but not necessary)syntacticconditions for reducible terms. Finally, we generalise these results to a language with recursion.     

Mechanizing a Process Algebra for Network Protocols

This paper presents the mechanization of a process algebra for Mobile Ad hoc Networks and Wireless Mesh Networks, and the development of a compositional framework for proving invariant properties. Mechanizing the core process algebra in Isabelle/HOL is relatively standard, but its layered structure necessitates special treatment. The control states of reactive processes, such as nodes in a network, are modelled by terms of the process algebra. We propose a technique based on these terms to streamline proofs of inductive invariance. This is not sufficient, however, to state and prove invariants that relate states across multiple processes (entire networks). To this end, we propose a novel compositional technique for lifting global invariants stated at the level of individual nodes to networks of nodes.     

有限布尔代数上的线性自动机

自动机理论是计算机科学理论的重要组成部分。论文研究了布尔代数上的线性自动机,证明了任意一个线性有限自动机是函数布尔代数上的一个内动机。定出了有限布尔代数上的一类可逆线性内动机,给出并证明了有限布尔代数上内动机图型为下向森林的充分必要条件,给出了树型内动机中每一层节点数的计算公式,进而证明了有限布尔代数上的非可逆内动机图型为恰等叉支下向树的充分必要条件。     

Action Refinement for Real-Time Concurrent Processes with Urgency

Action refinement for real=time concurrent processes with urgent interactions is studied, where a partial-order setting, i.e., timed bundle event structures, is used as the system model and a real-time LOTOS-like process algebra is used as the specification language. It is shown that the proposed refinement approaches have the commonly expected properties:(1) the behaviour of the refined process can be inferred compositionally from the behaviour of the original process and from the behaviour of the processes substituted for actions; (2) the timed extensions of pomset (partially ordered multiset) trace equivalence and history preserving bisimulation equivalence are both congruences under the refinement; (3) the syntactic and semantic refinements coincide up to the aforementioned equivalence relations with respect to a cpo-based denotational semantics.     

基于进程代数的软件动态演化模型初探

许多软件系统由于需求和执行环境的变化,都需要在运行时动态的演化.因此确保软件在演化时以及演化后可以正确的执行变得十分重要.最近Zhang Ji提出一种基于状态的软件动态演化模型,论文尝试建立一种基于进程代数的动态演化模型,并主要以原文中的实例为基础,通过进程代数对其进行建模以及分析,为最终建立此模型积累一定的经验.     

Constructions in Finite Geometry Using Computer Algebra Systems

One way of using a computer algebra system to do research in finite geometry is to use the system to construct “small" order examples of various constructions, and then hope to recognize a pattern that can be generalized and eventually proven. Of course, initially one does not know if the “small" order examples exist. However, if one has sufficiently good insight concerning where to look and a reasonably good “starter", the computer algebra system will often find these examples quite expeditiously. Once found the system can then be used to analyze the constructs. Brute-force searching, on the other hand, is typically foolhardy with such general purpose systems. These ideas will be illustrated with two problems in finite geometry: (1) finding new translation planes by a technique called “nesting", and (2) finding large collections of pairwise disjoint projective bundles of conics.     

A Process Algebra for Timed Systems

A standard process algebra is extended by a new action σ which is meant to denote idling until the next clock cycle. A semantic theory based on testing is developed for the new language. This is characterised in terms of barbs, a variety of ready traces and also characterised as the initial theory generated by a set of equations.     

Prajna: Adding Automated Reasoning to the Visual- Analysis Process

Applications and systems can represent knowledge in various ways. Graphic displays might help a data analyst infer new information through interactive visualizations. Knowledge represented as a collection of facts can be used for automatic inference, although it might be represented or stored in various archives, such as databases or formatted files. Developers who create applications for knowledge representation frequently must contend with not only data challenges but also challenges caused by a wide variety of software toolkits, architectures, and standards for knowledge representation. To overcome these obstacles, Vision Systems & Technology, Inc. initiated the Prajna project. The result was a Java toolkit designed to provide various capabilities for visualization, knowledge representation, geographic displays, semantic reasoning, and data fusion. This article is part of a special issue on knowledge-assisted visualization.     

进程代数上的抽象安全性质

在进程代数框架内基于算子的性质研究抽象安全性质及其偏序关系,定义了复合不变安全性质和可构造安全性质．首先证明进程代数算子在安全性质集是单调衰减算子．根据这一结果证明了复合不变性质和可构造安全性质在安全性质集上的存在性,并且在安全性质集合上证明了安全性质的“木桶原理”,即复合系统的整体安全性不强于系统中最弱的部分．基于安全性质之间的偏序关系,将所谓绝对安全性质与平凡性质联系起来,证明绝对安全性质是一类平凡性质．     

Implementation of a Formal Security Policy Refinement Process in WBEM Architecture

Security mechanisms enforcement consists in configuring devices with the aim that they cooperate and guarantee the defined security goals. In the network context, this task is complex due to the number, the nature, and the interdependencies of the devices to consider. In previous papers, we have proposed a formal framework that focuses on network security information management refinement. The framework includes three abstraction levels: the network security objectives, the network security tactics, and the network security device configurations. The information models of each abstraction level (consistency, correctness and feasibility) are formally specified and analyzed. In this paper we present the integration of this formal refinement process in the WBEM initiative in order to provide a management infrastructure that guarantees the validity of the deployed security configurations.     

Taking Decisions Late: End-Based Choice Combined with Action Refinement

A choice in concurrent systems is usually taken by the starting of an action. We propose the alternative view that a choice is determined by the ending of actions as this alternative has relevant applications and interesting implications. The different points of view lead in particular to different refinement operators.We introduce a refinement operator on bundle event structures for the end-based view. The standard equivalences are not preserved by this refinement operator. Therefore, we also introduce and study new equivalences that are preserved by our refinement operator.     

A Petri Net Semantics of a Simple Process Algebra for Mobility

In this paper, we propose a structural translation of terms from a simple variant of the Klaim process algebra into behaviourally equivalent finite high level Petri nets. This yields a formal semantics for mobility allowing one to deal directly with concurrency and causality.