Automata and processes on multisets of communicating objects

Inspired by P systems initiated by Gheorghe Pãun, we study a computation model over a multiset of communicating objects. The objects in our model are instances of finite automata. They interact with each other by firing external transitions between two objects. Our model, called a service automaton, is intended to specify, at a high level, a service provided on top of network devices abstracted as communicating objects. We formalize the concept of processes, running over a multiset of objects, of a service automaton and study the computing power of both single-process and multiprocess service automata. In particular, in the multiprocess case, regular maximal parallelism is defined for inter-process synchronization. It turns out that single-process service automata are equivalent to vector addition systems and hence can define nonregular processes. Among other results, we also show that Presburger reachability problem for single-process service automata is decidable, while it becomes undecidable in the multiprocess case. Hence, multiprocess service automata can not be effectively simulated by vector addition systems.     

DNA computing, sticker systems, and universality

We introduce the sticker systems, a computability model, which is an abstraction of the computations using the Watson-Crick complementarity as in Adleman's DNA computing experiment, [1]. Several types of sticker systems are shown to characterize (modulo a weak coding) the regular languages, hence the power of finite automata. One variant is proven to be equivalent to Turing machines. Another one is found to have a strictly intermediate power. Received: 10 October 1996 / 16 April 1997     

Verifying parallel programs with dynamic communication structures

We address the verification problem of networks of communicating pushdown systems modeling communicating parallel programs with procedure calls. Processes in such networks can read the control state of the other processes according to a given communication structure (specifying the observability rights between processes). The reachability problem of such models is undecidable in general. First, we define a class of networks that effectively preserves recognizability (hence, its reachability problem is decidable). Then, we consider networks where the communication structure can change dynamically during the execution according to a phase graph. The reachability problem for these dynamic networks being undecidable in general, we define a subclass for which it becomes decidable. Then, we consider reachability when the switches in the communication structures are bounded. We show that this problem is undecidable even for one switch. We define a natural class of models for which this problem is decidable. This class can be used in the definition of an efficient semi-decision procedure for the analysis of the general model of dynamic networks. Our techniques allowed to find bugs in two versions of a Windows NT Bluetooth driver.     

A quick introduction to membrane computing

Membrane computing is a branch of natural computing inspired from the architecture and the functioning of biological cells. The obtained computing models are distributed parallel devices, called P systems, processing multisets of objects in the compartments defined by hierarchical or more general arrangements of membranes. Many classes of P systems were investigated – mainly from the point of view of computing power and computing efficiency; also, a series of applications (especially in modeling biological processes) were reported. This note is a short and informal introduction to this research area, introducing a few basic notions, research topics, types of results, and pointing out to some relevant references.     

Performance bottlenecks and potentials of parallel computing on networks of workstations

The network of workstations (NOW) we consider for parallel computing is heterogeneous and nondedicated (time-sharing), where computing power varies among the workstations, and multiple jobs may interact with each other in execution. We address three performance issues in this paper. First, we examine the effects of heterogeneity on co-scheduling and local scheduling policies for parallel computing. Through experimentation and quantitative comparisons, we discuss features and requirements of scheduling policies on heterogeneous NOW. Second, the heterogeneity and non-dedication of NOW introduce new performance factors into parallel computing, which make traditional performance metrics for parallel computing under homogeneous platforms not suitable. We conducted a collection of experimental measurements to show the performance impact to parallel computing. Finally, using network latencies we experimentally evaluate the parallel computing scalability on NOW. Our objective of this study is to provide insights into unique performance bottlenecks and potentials of networks of workstations.     

基于上下文定界的Fork/Join并行性的并发程序可达性分析

随着多核技术日益发展,并发程序通过引入Fork/Join并行性,将任务分解为更细粒度的子任务并行执行,从而充分利用多核处理器提供的计算性能。并发执行线程之间的交错可能产生隐匿的程序设计错误,因此有必要对此类并发程序的正确性进行分析。上下文定界分析方法是一种检测并发程序中隐匿错误的高效方法,计算线程有限次上下文切换内的可达状态,确定错误状态是否可达。针对Fork/Join并行性的并发程序的可达性分析思想如下:首先,动态并发程序被建模为可模拟线程Fork/Join操作的动态并发下推系统P;然后从P中提取模拟其k-定界执行的并发下推系统Pk。现有的上下文定界可达算法可解决提取后的并发下推系统的k-定界可达性问题。     

BACH:线性混成系统有界可达性模型检验工具

混成自动机的模型检验问题非常困难,即使是其中相对简单的一个子类--线性混成自动机,它的可达性问题仍然是不可判定的.现有的相关工具大都使用多面体计算来判定线性混成自动机状态空间的可达集,复杂度高、效率低,无法解决实际应用规模的问题.描述了一个面向线性混成系统有界可达性模型检验工具--BACH(bounded reacha...     

Computing with energy and chemical reactions

Taking inspiration from some laws of Nature—energy transformation and chemical reactions—we consider two different paradigms of computation in the framework of Membrane Computing. We first study the computational power of energy-based P systems, a model of membrane systems where a fixed amount of energy is associated with each object and the rules transform objects by manipulating their energy. We show that if we assign local priorities to the rules, then energy-based P systems are as powerful as Turing machines; otherwise, they can be simulated by vector addition systems, and hence are not universal. Then, we consider stochastic membrane systems where computations are performed through chemical networks. We show how molecular species and chemical reactions can be used to describe and simulate the functioning of Fredkin gates and circuits. We conclude the paper with some research topics related to computing with energy-based P systems and with chemical reactions.     

Hierarchical CPU utilization control for real-time guarantees in power grid computing

Blackouts in our daily life can be disastrous with enormous economic loss. Blackouts usually occur when appropriate corrective actions are not effectively taken for an initial contingency. Therefore, it is critical to complete those tasks that are running power grid computing algorithms in the Energy Management System (EMS) in a timely manner to avoid blackouts. This problem can be formulated as guaranteeing end-to-end deadlines in a Distributed Real-time Embedded (DRE) system. However, existing feedback scheduling algorithms in DRE systems cannot be directly adopted to handle with significantly different timescales of power grid computing tasks. In this paper, we propose a hierarchical control solution to guarantee the deadlines of those tasks in EMS by grouping them based on their characteristics. Furthermore, we present an adaptive control scheme to achieve analytical assurance of control accuracy and system stability, in spite of significant system variation. Our solution is based on well-established control theory for guaranteed control accuracy and system stability and can adapt to changes in the system model without manual reconfiguration and profiling. Simulation results based on a realistic workload configuration demonstrate that our solution can guarantee timeliness for power grid computing and hence help to avoid blackouts.     

Asynchronous spiking neural P systems

We consider here spiking neural P systems with a non-synchronized (i.e., asynchronous) use of rules: in any step, a neuron can apply or not apply its rules which are enabled by the number of spikes it contains (further spikes can come, thus changing the rules enabled in the next step). Because the time between two firings of the output neuron is now irrelevant, the result of a computation is the number of spikes sent out by the system, not the distance between certain spikes leaving the system. The additional non-determinism introduced in the functioning of the system by the non-synchronization is proved not to decrease the computing power in the case of using extended rules (several spikes can be produced by a rule). That is, we obtain again the equivalence with Turing machines (interpreted as generators of sets of (vectors of) numbers). However, this problem remains open for the case of standard spiking neural P systems, whose rules can only produce one spike. On the other hand we prove that asynchronous systems, with extended rules, and where each neuron is either bounded or unbounded, are not computationally complete.For these systems, the configuration reachability, membership (in terms of generated vectors), emptiness, infiniteness, and disjointness problems are shown to be decidable. However, containment and equivalence are undecidable.     

Rewriting in the partial algebra of typed terms modulo AC

We study the partial algebra of typed terms with an associative commutative and idempotent operator (typed AC-terms). The originality lies in the representation of the typing policy by a graph which has a decidable monadic theory.In this paper we show on two examples that some results on AC-terms can be raised to the level of typed AC-terms. The examples are the results on rational languages (in particular their closure by complement) and the property reachability problem for ground rewrite systems (equivalently process rewrite systems).     

Object tracking method based on data computing

The data computing process is utilized in various areas such as autonomous driving. Autonomous vehicles are intended to detect and track nearby moving objects avoiding collisions and to navigate in complex situations, such as heavy traffic and dense pedestrian areas. Therefore, object tracking is the core technology in the environment perception systems of autonomous vehicles and requires the monitoring of surrounding objects and the prediction of the moving states of objects in real time. In this paper, a multiple object tracking method based on light detection and ranging (LiDAR) data is proposed by using a Kalman filter and data computing process. We suppose that the movements of the tracking objects are captured consecutively as frames; thus, model-based detection and tracking of dynamic objects are possible. A Kalman filter is applied for predicting posterior state of tracking object based on anterior state of the tracking object. State denotes the positions, shapes, and sizes of objects. By computing the likelihood probability between predicted tracking objects and clusters which registered from tracking objects, the data association process of the tracking objects can be generated. Experimental results showed enhanced object tracking performance in a dynamic environment. The average matching probability of the tracking object was greater than 92.9%.

     

On Symbolic Verification of Weakly Extended PAD

We consider the verification problem of a class of infinite-state systems called wPAD. These systems can be used to model programs with (possibly recursive) procedure calls and dynamic creation of parallel processes. They correspond to PAD models extended with an acyclic finite-state control unit, where PAD models can be seen as combinations of prefix rewrite systems (pushdown systems) with context-free multiset rewrite systems (synchronization-free Petri nets). Recently, we have presented symbolic reachability techniques for the class of PAD based on the use of a class of unranked tree automata. In this paper, we generalize our previous work to the class wPAD which is strictly larger than PAD. This generalization brings a positive answer to an open question on decidability of the model checking problem for wPAD against EF logic. Moreover, we show how symbolic reachability analysis of wPAD can be used in (under) approximate analysis of Synchronized PAD, a (Turing) powerful model for multithreaded programs (with unrestricted synchronization between parallel processes). This leads to a pragmatic approach for detecting the presence of erroneous behaviors in these models based on the bounded reachability paradigm where the notion of bound considered here is the number of synchronization actions.     

E-mc2: A formal framework for energy modelling in cloud computing

Due to energy crisis of the last years, energy waste and sustainability have been brought both into public attention, and under industry and scientific scrutiny. Thus, obtaining high-performance at a reduced cost in cloud environments as reached a turning point where computing power is no longer the most important concern. However, the emphasis is shifting to manage energy efficiently, whereas providing techniques for measuring energy requirements in cloud systems becomes of capital importance.Currently there are different methods for measuring energy consumption in computer systems. The first consists in using power meter devices, which measure the aggregated power use of a machine. Another method involves directly instrumenting the motherboard with multimeters in order to obtain each power connector’s voltage and current, thus obtaining real-time power consumption. These techniques provide a very accurate results, but they are not suitable for large-scale environments. On the contrary, simulation techniques provide good scalability for performing experiments of energy consumption in cloud environments. In this paper we propose E-mc², a formal framework integrated into the iCanCloud simulation platform for modelling the energy requirements in cloud computing systems.     

基于二叉决策图的网络可达性计算

针对现有攻击图生成方法中普遍通过网络扫描获得网络可达性信息存在信息不完整、耗时长、产生网络干扰等不足,提出一种基于二叉决策图的网络可达性计算方法。该方法利用二叉决策图建模防火墙规则,通过高效的集合运算计算网络可达性。真实环境检测和模拟实验均表明该方法具有精确、耗时短、无网络干扰等优点,适用于大规模网络可达性的计算,推动了攻击图在大规模网络中的应用。     

Locating objects in mobile computing

In current distributed systems, the notion of mobility is emerging in many forms and applications. Mobility arises naturally in wireless computing since the location of users changes as they move. Besides mobility in wireless computing, software mobile agents are another popular form of moving objects. Locating objects, i.e., identifying their current location, is central to mobile computing. We present a comprehensive survey of the various approaches to the problem of storing, querying, and updating the location of objects in mobile computing. The fundamental techniques underlying the proposed approaches are identified, analyzed, and classified along various dimensions     

Supervisory control of deterministic Petri nets with regularspecification languages

Algorithms for computing a minimally restrictive control in the context of supervisory control of discrete-event systems have been well developed when both the plant and the desired behaviour are given as regular languages. In this paper the authors extend such prior results by presenting an algorithm for computing a minimally restrictive control when the plant behaviour is a deterministic Petri net language and the desired behaviour is a regular language. As part of the development of the algorithm, the authors establish the following results that are of independent interest: i) the problem of determining whether a given deterministic Petri net language is controllable with respect to another deterministic Petri net language is reducible to a reachability problem of Petri nets and ii) the problem of synthesizing the minimally restrictive supervisor so that the controlled system generates the supremal controllable sublanguage is reducible to a forbidden marking problem. In particular, the authors can directly identify the set of forbidden markings without having to construct any reachability tree     

Languages generated by P systems with active membranes

We propose an alternative approach to generate languages by means of P systems: building up an appropriate representation for a string by means of a corresponding membrane structure and then generating the string by visiting the membrane structure according to a well-specified strategy. To this aim, we consider P systems with active membranes, allowing membrane creation or division or duplication and dissolution, where the output of a computation may be obtained either by visiting the tree associated with the membrane structure, or by following the traces of a specific object, called traveller, or sending out the objects. For each of these approaches, we provide characterizations of recursively enumerable languages based on P systems that use different sets of operations for modifying the membrane structure. Francesco Bernardini: He started his Ph.D. at the University of Sheffield in December 2002 after having previously got a master degree in Computer Science from the University of Pisa in Italy. His research is dedicated to the study of theoretical aspects of membrane computing (P systems) and discrete models of biological systems based on P systems. Marian Gheorghe, Ph.D.: His main research interests are in computational models and their applications to software modelling and testing, formal specifications of agent based systems, software engineering. He was investigating computational power of various generative devices (regular, context-free, fully initial; grammar systems; L-systems and variants). He is currently interested in natural computing (membrane calculus) and biological modelling.     

Context-aware trails [mobile computing]

The emergence of converged mobile devices with a wide range of computing, communications, entertainment, and sensing capabilities represents a major step in the evolution of wireless computing. Such devices increasingly shift the decision-making power from the user to the machine, which has the capacity to be better informed about the current environment and can respond more quickly. A trail is a collection of locations, together with associated information about these locations and a recommended order for visiting them. Mobile, context-aware trails-based applications range from single-user systems that focus on individual daily activities to multimedia groupware that supports a wide collection of user requirements. The trails metaphor makes it possible to explore adaptive characteristics common to all mobile, context-aware applications. Adaptation in this context involves altering the set of interest points on a trail and their visiting order with timeliness, accuracy, and relevance while remaining in tune with user expectations.     

Location-based services in ubiquitous computing environments

This paper presents a framework for providing dynamically deployable services in ubiquitous computing settings. The goal of the framework is to provide people, places, and objects with computational functionalities to support and annotate them. Using RFID-based tracking systems, the framework detects the locations of physical entities, such as people or things, and deploys services bound to the entities at proper computing devices near where they are located. It enables location-based and personalized information services to be implemented as mobile agents and operated at stationary or mobile computing devices, which are at appropriate locations, even if the services do not have any location-information. This paper presents the rationale, design, implementation, and applications of our prototype infrastructure.