Structured Modeling with Hyperdag P Systems: Part A

Abstract

P systems provide a computational model based on the structure and interaction of living cells. A P system consists of a hierarchical nesting of cell-like membranes, which can be visualized as a rooted tree. Although the P systems are computationally complete, many real world models, e.g., from socio-economic systems, databases, operating systems, distributed systems, seem to require more expressive power than provided by tree structures. Many such systems have a primary tree-like structure completed with shared or secondary communication channels. Modeling these as tree-based systems, while theoretically possible, is not very appealing, because it typically needs artificial extensions that introduce additional complexities, nonexistent in the originals. In this paper we propose and define a new model that combines structure and flexibility, called hyperdag P systems, in short, hP systems, which extend the definition of conventional P systems, by allowing dags, interpreted as hypergraphs, instead of trees, as models for the membrane structure. We investigate the relation between our hP systems and neural P systems. Despite using an apparently less powerful structure, i.e., a dag instead of a general graph, we argue that hP systems have essentially the same computational power as tissue and neural P systems. We argue that hP systems offer a structured approach to membrane-based modeling that is often closer to the behavior and underlying structure of the modeled objects. Additionally, we enable dynamical changes of the rewriting modes (e.g., to alternate between determinism and parallelism) and of the transfer modes (e.g., the switch between unicast or broadcast). In contrast, classical P systems, both tree and graph based P systems, seem to focus on a statical approach. We support our view with a simple but realistic example, inspired from computer networking, modeled as a hP system with a shared communication line (broadcast channel). In Part B of this paper we will explore this model further and support it with a more extensive set of examples.