Mobility in process calculi and natural computing. (Q653874)

Chapter 1 (Mobility in process calculi) deals, as the title says, with mobility in various process calculi. It starts with the \(\pi\)-calculus as a formalism in which processes can send each other also communication links and in this way one can express moving processes both in a physical space of computing locations and in a virtual space of linked processes. Then the timed distributed \(\pi\)-calculus is presented. It contains two kinds of timers: the timers on channels define timeouts for communications, and timers on the channel types restrict the channel availability. Mobile ambinets and mobile ambients with timers follow and the chapter is concluded with brane calculi. The next chapter (Mobility in membrane computing), after short biological motivations, introduces basics of membrane computing and then it concentrates on mobile membranes. Computability power of mobile membranes and some complexity problems (as SAT, 2QBT, bin packing, subset sum, knapsack and 2-partition problem) of mutual mobile membranes are discussed. At the end some decidability results (reduction of replication rules for mobile membranes with replication and reachability) are presented. The third and last chapter is devoted to various encodings (distributed \(\pi\)-calculus into timed distributed \(\pi\)-calculus, pure mobile ambients into \(\pi\)-calculus, safe mobile ambients into mutual mobile membranes, branes into mobile membranes with objects on surface, and mobile membranes with objects on surface into Petri nets).