Correctness of concurrent processes

A new notion of correctness for concurrent processes is introduced and investigated. It is a relationship P sat S between process terms P built up from operators of CCS [24], CSP [18] and COSY [20] and logical formulas S specifying sets of finite communication sequences as in [38]. The definition of P sat S is based on a Petri net semantics for process terms [27]. The main point is that P sat S requires a simple liveness property of the net denoted by P. This implies that P is divergence free and externally deterministic. Process correctness P sat S determines a new semantic model for process terms and logical formulas. It is a modification ^* of the readiness semantics [28] which is fully abstract with respect to the relation P sat S. The model ^* abstracts from the concurrent behaviour of process terms and certain aspects of their internal activity. In ^* process correctness P sat S boils down to semantic equality: ^*P = ^*S. The modified readiness equivalence is closely related to failure equivalence [7] and strong testing equivalence [9].     

Calculi for Concurrent Processes

InmytalkIsurveyedsomeofthemainstreamresearchthathasbeendoneintheareaofprocesscalculiduringthelasttwentyyears-thoughfocusingonsomelastdevelopments,regardingespeciallymobilecomputing.IstartedwithabriefaccountofthepioneeringworkofMimerandhisco-workersonCCS,theCalculusofCommunicatingSystems.ThisbeguninthelateseventieswhenMimerrealizedthatScott'sdenotationalsemanticswasnotsofruitfulconcerningconcurrency.ApreliminarystepwastakenbyMilnerwithhisflowalgebra,consistingofasmallsetofoperationsandaxiom…     

A transformation system for concurrent processes

Program transformation techniques have been extensively studied in the framework of functional and logic languages, where they were applied mainly to obtain more efficient and readable programs. All these works are based on the Unfold/Fold program transformation method developed by Burstall and Darlington in the context of their recursive equational language. The use of Unfold/Fold based transformations for concurrent languages is a relevant issue that has not yet received an adequate attention. In this paper we define a transformation methodology for CCS. We give a set of general rules which are a specialization of classical program transformation rules, such as Fold and Unfold. Moreover, we define the general form of other rules, “oriented” to the goal of a transformation strategy, and we give conditions for the correctness of these rules. We prove that a strategy using the general rules and a set of goal oriented rules is sound, i.e. it transforms CCS programs into equivalent ones. We show an example of application of our method. We define a strategy to transform, if possible, a full CCS program into an equivalent program whose semantics is a finite transition system. We show that, by means of our methodology, we are able to a find finite representations for a class of CCS programs which is larger than the ones handled by the other existing methods. Our transformational approach can be seen as unifying in a common framework a set of different techniques of program analysis. A further advantage of our approach is that it is based only on syntactic transformations, thus it does not requires any semantic information. Received: 24 April 1997 / 19 November 1997     

Towards a language for concurrent processes

In this paper we shall discuss concurrency in programming languages, with a view towards designing a process-oriented language which, by its inherent parallelism, is well suited to exploit the forthcoming generation of distributed processor networks. We shall start by discussing the traditional approach towards managing concurrency, with ‘monitors’ co-ordinating the interactions of ‘processes’, and shall demonstrate that this approach actually degrades concurrency by imposing sequentiality during interactions because it is based on the premise of co-ordinating secure access to shared resources. As a tool for interprocess communication it is felt that the ‘monitor’ is too far removed from the abstract nature of the problem, and so, as a purely engineering solution, it imposes too broad and too prolonged an exclusion to be acceptable in general. Instead we turn to a simpler, and ultimately more powerful notion of ‘message passing’ between parallel processes. We shall show how, if the message system is polymorphic, any data value, however large it is, can pass freely between any pair of processes. By making the processes themselves values in the language we shall discover that message networks can come into being dynamically, and tailor themselves to their applications as and when necessary by ‘short-circuiting’ extensive communications paths. We shall also see how, if the message system is inherently asynchronous, the degree of the parallelism in a system can be enhanced, not degraded, as more and elaborate communications paths develop, the only sequentiality in the system as a whole being imposed by synchronizing processes, not the message passing system itself. After discussing the various built-in system facilities that permit processes to dynamically find out about and study one another, thus permitting processes to set up and thereafter supervise whole subsystems, we shall round off by discussing the advantages of introducing the machines themselves into the language, making it possible for processes to become aware of, and then ‘migrate’ within, the topological structure of a multi-processor distributed network, moving closer to their application, or just to a less-loaded processor, as the need arises. To conclude we shall contrast this new-style process-oriented language with various existing programming languages which have experimented with concurrency, either implicitly or explicitly, in order to see if, and if so how, this new style is any simpler and more powerful than its precursors.     

Modeling concurrent real-time processes using discrete events

We give a formal framework for studying real-time discrete-event systems. It describes concurrent processes as sets of possible behaviors. Compositions of processes are processes with behaviors in the intersection of the behaviors of the component processes. The interaction between processes is through signals, which are collections of events. Each event is a value-tag pair, where the tags denote time. Zeno conditions are defined and methods are given for avoiding them. Strict causality ensures determinacy under certain technical conditions, and delta-causality ensures the absence of Zeno conditions. This revised version was published online in June 2006 with corrections to the Cover Date.     

基于演化母板的通用演化硬件平台研究

作为一种新型的理论研究和实践技术,演化硬件(EHW)在机器学习、人工神经网络、自适应控制、信号处理与识别、容错系统和机器人等方面已经受到了广泛的重视。本文针对FPGA等商用可编程逻辑器件在演化硬件研究中出现的种种问题,提出一个基于演化母板的新型演化平台,并介绍了它的系统结构及工作原理。     

CONCUR: A language for continuous, concurrent processes

Hendrix's robot modeling system presented a simulation method in which time is represented as a continuous phenomenon. This paper introduces the language CONCUR, which realizes Hendrix's concept through an extension of the LISP environment. CONCUR uses generalized procedures (scenarios) operating in a data-driven mode to implement Hendrix's events. The heart of CONCUR is a generalized pattern-matcher which permits operators within the patterns to bind variables and modify the match process. We include several detailed examples in addition to an implementation of the pattern matcher.     

Evolvable Hardware in Evolutionary Robotics

In recent decades the research on Evolutionary Robotics (ER) has developed rapidly. This direction is primarily concerned with the use of evolutionary computing techniques in the design of intelligent and adaptive controllers for robots. Meanwhile, much attention has been paid to a new set of integrated circuits named Evolvable Hardware (EHW), which is capable of reconfiguring its architectures unlimited time based on artificial evolution techniques. This paper surveys the application of evolvable hardware in evolutionary robotics. The evolvable hardware is an emerging research field concerning the development of evolvable robot controllers at the hardware level to adapt to dynamic changes in environments. The context of evolvable hardware and evolutionary robotics is reviewed, and a few representative experiments in the field of robotic hardware evolution are presented. As an alternative to conventional robotic controller designs, the potentialities and limitations of the EHW-based robotic system are discussed and summarized.     

A concurrent engineering approach to selective implementation of alternative processes

During the last decade, integration between design and manufacturing has shown to be a major competitive weapon and much research work has been carried out about considering at the product design stage production process issues.Most of the literature on such techniques focuses on integrating the design of a product and the design of its manufacturing processes, disregarding issues related to the design and management of the manufacturing system. Nonetheless, decisions taken at the product and process design stage could have an influence on typical production planning and control issues such as, for example, minimising lead times and maximising machine utilisation.Many research works show the advantage of a higher process flexibility, in terms of machine utilisation, manufacturing lead time, inventory level, and the like (see, for example, Tsubone and Horikawa, The International Journal of Flexible Manufacturing Systems 11 (1999) 83 or Ferreira and Wysk, Journal of Manufacturing System 19 (2001)), but developing alternative machine possibility has a cost that is not negligible (International Journal of Production Economics 48 (1997) 237). Therefore, guidelines are needed for identifying for what items and for which operations to develop alternative processes.In this paper, the relationship between alternative processes availability and manufacturing system performances are investigated, showing that the advantage of additional alternative process decreases as the number of alternatives increases, and that given a certain number of alternative processes developed, there is a strong difference in performances depending on what alternative processes have been implemented. Then a new procedure is presented for guiding in selecting for which operations to implement alternative processes in order to maximise the flexibility advantages limiting the implementation cost.The proposed procedure is then tested, under different operating conditions, against a practical rule by means of a simulation model.     

Infinitely running concurrent processes with loops from a geometric viewpoint

This report gives a formal topological semantics to inductively defined concurrent systems and investigates the properties of such systems. We allow loops and infinitely running computations, which is new in the topological investigations of concurrency. In this more general setting, we prove the equivalent to the result from [2] that deadlocks and unsafe points can be found using a finite number of deloopings.     

基于演化硬件的图像加密技术研究

本文将演化硬件和细胞自动机图像加密相结合,提出了一种将演化硬件应用到图像加密中的新技术。通过对基本逻辑电路的演化找出正确的加密规则(搜索密钥),继而采用反向迭代加密技术对图像进行加密和解密。演化硬件既可以作为搜索密钥工具,也可以作为规则表的逻辑电路,密钥更换时不需要更换硬件,增加了硬件的重用性,而且实现了密钥分散,使加密安全性得到了增强。实验证实了该技术的可行性,取得了良好的加密效果。     

进化型硬件的一种实现方法

遗传算法和可编程器件的融合,形成了进化型硬件。本文介绍采用可编程器件GAL16V8实现硬件进化的方法和系统构成,并使其中一个逻辑宏单元成功地进化成8选1多路选择器。     

A Scalable Approach to Evolvable Hardware

Evolvable Hardware (EHW) has been proposed as a new method for designing systems for complex real-world applications. However, so far, only relatively simple systems have been shown to be evolvable. In this paper, it is proposed that concepts from biology should be applied to EHW techniques to make EHW more applicable to solving complex problems. One such concept has led to the increased complexity scheme presented, where a system is evolved by evolving smaller sub-systems. Experiments with two different tasks illustrate that inclusion of this scheme substantially reduces the number of generations required for evolution. Further, for the prosthesis control task, the best performance is obtained by the novel approach. The best circuit evolved performs better than the best trained neural network.     

树型编码在演化硬件中的应用

演化硬件的难点在于,当目标电路比较复杂时,解空间急骤增大,目前常用的演化方法及编码都存在一定的缺陷,可靠性不强。三元组编码是目前比较典型的一种方法,通过实验验证,在求解复杂问题时可靠性也不强,因此针对三元组编码提出一种改进策略,即利用树型结构对算法加以改进,提高算法可靠性,最终演化出消耗资源最少的数字电路.实验证明,算法改进是有效的,改进后的算法结果优于现有算法。     

基于被动-主动的特征演化流学习

在许多现实应用中,数据以一种特征演化流的形式收集.例如,随着传感器的更换,由旧传感器收集的数据特征会消失,新传感器收集的数据特征会出现.在线被动-主动算法已被证明可以有效地从具有固定特征空间和梯形特征空间的数据集中学习线性分类器.因此,提出了一种基于被动-主动更新策略的特征演化学习算法(passive-aggressive learning with feature evolvable streams, PAFE).该算法通过主动-被动更新策略从当前特征空间和被恢复的已消失特征空间中学习了2个模型.具体来说,在重叠时段,即新旧特征同时存在的时段,该算法用新特征恢复了消失的特征空间,同时用旧特征空间模拟了新特征空间,进而为新特征空间的模型学习提供合理的初始化.基于这2个模型,为提高算法整体性能提出了2个集成算法：组合预测和当前最优预测.在合成数据集和真实数据集上的实验结果验证了该算法的有效性.