Generalized P colony automata, a nature motivated computational model based on multiset processing

Dátum
2014-04-10T13:57:29Z
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
Absztrakt

Nature-inspired models have recently gained momentum in composing, coordinating and adapting the “Internet of Services”, where a myriad of services and users are interacting autonomously, exhibiting properties that might assist with programming a global computing platform. The virtual communication world has been overtaken by applications and it is no longer operating the way we were using it in the last two decades. Instead of just surfing, we are accessing a service through application. Internet as a computing platform has become an ecosystem comprising a myriad of heterogeneous and autonomous services encapsulating IT components such as storage space, computing power, software or sensors, which is exploited the best, if according to users’ requests, one composes, coordinates and adapts such services dynamically. A class of computational models which might be adequate to describe the scenario outlined above is based on what might be called a chemical paradigm of computing. This chemical approach is justified by the observation that chemistry concepts, which express dynamics, decentralization and parallelism, are similar to those appearing in this virtual ecosystem. Based on chemical laws, programs take place as connections between molecules that react with each other in an implicitly parallel, non-deterministic, autonomous and distributed way. The aim of this research was to come up with a new computational model, that takes this parallel and decentralized chemical metaphor into account. To this aim, we take automata-like variants of membrane systems (P systems) and P colonies as our starting point. These systems are nature motivated, unconventional computational models inspired by the structure and the functioning of living cells. They provide a formalization of the above mentioned chemical paradigm of computing in general, and their automatalike variants are designed to emphasize and capture the interaction between the system and its environment. This way they provide a description of a system of interacting agents, processes, or any kind of computational devices forming the elements of the interaction model which seems to be appropriate to give a kind of basis for the formal description of the virtual ecosystem of Future Internet sketched above. In this study, we introduce a generalized variant of P colony automata, provide results on their computational power, and compare them to other automata-like variants of the P systems model. Our results not only give a characterization of the limits of this type of chemical computational approach, but also help to classify these P system models, to understand their properties and the way they influence their computational/descriptive power. The work is organized as follows: the second chapter gives some motivation and a short introduction to the chemical computing paradigm and membrane systems (P systems), P colonies in general. In the third chapter, we introduce the reader to generalized P colony automata and after the necessary definitions and some examples, we study the computational capabilities of three of their variants. We also compare our findings with the corresponding results on related models, namely, the related variants of P automata. We will see that (separating the description of the system and its environment) generalized P colony automata have an essentially more simple description than other P system variants (the number of objects inside the system is bounded by a finite constant), but still, their computational power can in many cases be similar.

Leírás
Kulcsszavak
nature motivated, automata theory, formal languages, P colony automata, membrane systems, membrán rendszerek, formális nyelvek és automaták, természet motiválta számítási modellek, chemical paradigm, kémiai paradigma
Forrás