Specification and refinement of mobile systems in MTLA and mobile UML

We define the spatio-temporal logic MTLA as an extension of Lamport's Temporal Logic of Actions TLA for the specification, verification, and formal development of systems that rely on mobile code. The formalism is validated by an encoding of models written in the mobile UML notation. We identify refinement principles for mobile systems and justify refinements of mobile UML state machines with the help of the MTLA semantics.     

Nonholonomic Mobile Manipulators: Kinematics, Velocities and Redundancies

We consider nonholonomic mobile manipulators built from an n _a joint robotic arm and a nonholonomic mobile platform with two independently driven wheels. Actually, there is no efficient kinematic formalism for these systems which are generally characterized by their high number of actuators. So, kinematic modelling is presented with particular emphasis on redundancy. Whereas kinematic redundancy is well known in the holonomic case, it is pointed out that it is necessary to define velocity redundancy in the case of nonholonomic systems. Reduced velocity kinematics based on quasi-velocities are shown to provide an efficient formalism. Two examples of mobile manipulators are presented. Finally, reduced velocity kinematics and velocity redundancy are shown to be adequate tools in order to realize operational task while optimizing criteria such as manipulability.     

Solving a weak NP-complete problem in polynomial time by using mutual mobile membrane systems

Mutual mobile membrane systems represent a variant of mobile membrane systems in which endocytosis and exocytosis work whenever the involved membranes ??agree?? on the movement by using mutual complement objects placed in membranes. We provide a semi-uniform polynomial solution for a weak NP-complete problem (namely partition problem) by means of mutual mobile membrane systems.     

Formalisms for Mobile Resource Control

Failing to control resources in mobile, concurrent and distributed systems may lead to important breakdowns or Denial of Service-like attacks. In order to address this problem, we present enhanced versions of several calculi for mobile and distributed computing, namely NBA, Seals, Nomadic π and Kells. In each case, we make the formalism resource-conscious and define a type system in order to guarantee statically compliance with resource control policies. Comparing the solutions we proposed for these calculi, we try and define the necessities of resource-control in mobile and distributed formalisms.     

Translating Mobile Ambients into P Systems

We present a translation of the mobile ambients without communication and replication into P systems with mobile membranes. We introduce a set of developmental rules over membranes, and describe the correspondence between the behaviour of an ambient and the evolution of its translated membrane system. We give an operational correspondence result between the mobile ambients and P systems.     

Mutual mobile membranes with objects on surface

In this paper we study systems of mutual mobile membranes with objects on surface using pino/exo/phago rules. Their rules are applicable whenever there is a mutual agreement between membranes expressed by appropriate objects and co-objects on their surfaces. We investigate the computational power of these systems, and also relate them to brane calculi by encoding the PEP fragment of brane calculus into the systems of mutual mobile membranes with objects on surface.     

On Composite Web Services Provisioning in an Environment of Fixed and Mobile Computing Resources

We present a framework for Web services provisioning in a hybrid environment of fixed and mobile computing resources. Several obstacles still hinder the seamless provisioning of Web services in mobile environments. Examples of such obstacles are: throughput and connectivity of wireless networks, limited computing resources of mobile devices, and risks of communication channel disconnections. In the proposed framework, software agents represent users, providers of services, and providers of resources. The business logic of composite services is expressed as a process model using statecharts formalism. Among other things, the use of agents provides an infrastructure that has the ability to handle disconnections during service preparation for execution. The framework also integrates a service execution planning approach to optimally select computing resources (fixed or mobile) on top of which services will be executed.     

Enhanced Mobile Membranes: Computability Results

The enhanced mobile membranes is a variant of membrane systems which has been proposed for describing some biological mechanisms of the immune system. In this paper, we study the computational power of the enhanced mobile membranes. In particular, we focus on the power of mobility given by the operations endo, exo, fendo and fexo. The computational universality is obtained with 12 membranes, while systems with 8 membranes subsume PsET0L, and those with 3 membranes are contained in PsMAT.     

Modeling the Exogenous Coordination of Mobile Channel-based Systems with Petri Nets

In this paper, we discuss how to model systems that communicate through and are coordinated by mobile channels. Mainly, we focus on modeling the exogenous coordination behavior imposed by these channels. We use Petri Nets as our modeling language, for they provide a graphically and mathematically founded modeling formalism. We give Petri Nets for a set of mobile channel types. This allows us to construct models of applications, by taking the Petri Net of each component and each mobile channel, and composing them together. For this purpose, we define a special Petri Net composition function. We also discuss analysis and simulation of these models and their exogenous coordination behavior.     

Membrane computing with transport and embedded proteins

In this paper, we look at the expressive power of P systems with proteins embedded on the membranes. The rules governing the evolution of the embedded proteins are inspired from brane calculi. We use some basic operations of brane calculi, namely, exo, endo, bud, mate, pino, wrap in the formalism of membrane computing. We also use rules allowing the movement of proteins, to pass through membranes and attach to and detach from the membranes. Combining the two kinds of operations, namely, brane calculi operations as well as protein movement operations, we have obtained some universality results of P systems. We have also identified some decidable sub-classes of P systems by restricting the use of the protein movement rules.     

Multimedia layout adaptation through grammatical specifications

Online multimedia presentations, such as news, need to be constantly updated. Increasing demands are also being made for accessing online multimedia documents from mobile devices such as PDAs. There is an urgent need for a sound but practical formalism that supports automatic adaptation to the change of media content, display environments, and user intention. This paper presents a visual language approach to the layout adaptation of multimedia objects. The underlying theory of our approach is a context-sensitive graph grammar formalism enriched with facilities for spatial representation and specification. The paper focuses on the issues and techniques for size adaptation and style adaptation in response to the change of device requirements and user interactions.Published online: 2 February 2005 Correspondence to: Kang Zhang     

Compositional programming abstractions for mobile computing

Recent advances in wireless networking technology and the increasing demand for ubiquitous, mobile connectivity demonstrate the importance of providing reliable systems for managing the reconfiguration and disconnection of components. The design of such systems requires tools and techniques appropriate to the task. Many formal models of computation, including UNITY, are not adequate for expressing reconfiguration and disconnection and are, therefore, inappropriate vehicles for investigating the impact of mobility on the construction of modular and composable systems. Algebraic formalisms such as the π-calculus have been proposed for modeling mobility. This paper addresses the question of whether UNITY, a state-based formalism with a foundation in temporal logic, can be extended to address concurrent, mobile systems. In the process, we examine some new abstractions for communication among mobile components that express reconfiguration and disconnection and which can be composed in a modular fashion     

Describing the Immune System Using Enhanced Mobile Membranes

We investigate the enhanced mobile membranes, a new class of mobile membrane system in which new rules are introduced. The contextual evolution rules describe how an object from a membrane can evolve only in some context. The other rules describe the objective endocytosis and exocytosis. We use the class of enhanced mobile membrane system to model some evolutions in the immune system.     

Reachability analysis of fragments of mobile ambients in AC term rewriting

In this paper, we investigate the connection between fragments of associative-commutative Term Rewriting and fragments of Mobile Ambients, a powerful model for mobile and distributed computations. The connection can be used to transfer decidability and undecidability results for important computational properties like reachability from one formalism to the other. Furthermore, it can be viewed as a vehicle to apply tools based on rewriting for the simulation and validation of specifications given in Mobile Ambients.     

Optimization algorithms for large-scale real-world instances of the frequency assignment problem

Nowadays, mobile communications are experiencing a strong growth, being more and more indispensable. One of the key issues in the design of mobile networks is the frequency assignment problem (FAP). This problem is crucial at present and will remain important in the foreseeable future. Real-world instances of FAP typically involve very large networks, which can be handled only by heuristic methods. In the present work, we are interested in optimizing frequency assignments for problems described in a mathematical formalism that incorporates actual interference information, measured directly on the field, as is done in current GSM networks. To achieve this goal, a range of metaheuristics have been designed, adapted, and rigourously compared on two actual GSM networks modeled according to the latter formalism. To generate quickly and reliably high-quality solutions, all metaheuristics combine their global search capabilities with a local-search method specially tailored for this domain. The experiments and statistical tests show that in general, all metaheuristics are able to improve upon results published in previous studies, but two of the metaheuristics emerge as the best performers: a population-based algorithm (Scatter Search) and a trajectory based (1+1) Evolutionary Algorithm. Finally, the analysis of the frequency plans obtained offers insight about how the interference cost is reduced in the optimal plans.     

Dynamical neural networks for planning and low-level robot control

We use dynamical neural networks based on the neural field formalism for the control of a mobile robot. The robot navigates in an open environment and is able to plan a path for reaching a particular goal. We will describe how this dynamical approach may be used by a high level system (planning) for controlling a low level behavior (speed of the robot). We give also results about the control of the orientation of a camera and a robot body.     

Reasoning about shadows in a mobile robot environment

This paper describes a logic-based formalism for qualitative spatial reasoning with cast shadows (Perceptual Qualitative Relations on Shadows, or PQRS) and presents results of a mobile robot qualitative self-localisation experiment using this formalism. Shadow detection was accomplished by mapping the images from the robot’s monocular colour camera into a HSV colour space and then thresholding on the V dimension. We present results of self-localisation using two methods for obtaining the threshold automatically: in one method the images are segmented according to their grey-scale histograms, in the other, the threshold is set according to a prediction about the robot’s location, based upon a qualitative spatial reasoning theory about shadows. This theory-driven threshold search and the qualitative self-localisation procedure are the main contributions of the present research. To the best of our knowledge this is the first work that uses qualitative spatial representations both to perform robot self-localisation and to calibrate a robot’s interpretation of its perceptual input.     

On the power and size of extended gemmating P systems

In [3] P systems with gemmation of mobile membranes were examined. It was shown that (extended) systems with eight membranes are as powerful as the Turing machines. Moreover, it was proved that extended gemmating P systems with only pre-dynamical rules are still computationally complete: in this case nine membranes are needed to obtain this computational power. In this paper we improve the above results concerning the size bound of extended gemmating P systems, namely we prove that these systems with at most five membranes (with meta-priority relations and without communication rules) form a class of universal computing devices, while in the case of extended systems with only pre-dynamical rules six membranes are enough to determine any recursively enumerable language.     

基于时间Ambient演算的业务流程模型验证

Mobile Ambient演算是一种描述进程和设备移动的形式化方法,但其移动进程的实时性目前尚未有合适的形式化表达.通过对Mobile Ambient演算进行实时扩充,提出了一种离散时间域的时间Mobile Ambient演算(DTMA),并为DTMA演算定义了模态逻辑.基于DTMA演算及其模态逻辑的子集给出了模型验证算法,提出了一种对BPEL4WS程序的形式化建模方法,实现了业务流程的活动可达性的模型验证.