Towards Structured Modelling with Hyperdag P Systems

  • Michael J. Dinneen Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand
  • Yun-Bum Kim Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand
  • Radu Nicolescu Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand


Although P systems are computationally complete, many real world models, such as socio-economic systems, databases, operating systems and distributed systems, seem to require more expressive power than provided by tree structures. Many such systems have a primary tree-like structure augmented with shared or secondary communication channels. Modelling these as tree-based systems, while theoretically possible, is not very appealing, because it typically needs artificial extensions that introduce additional complexities, inexistent in the originals. In this paper, we propose and define a new model 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 restricted 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 membranebased modelling that is often closer to the behavior and underlying structure of the modelled objects.


[1] C. Berge, Hypergraphs: Combinatorics of Finite Sets, Elsevier Science Publishers, 1989.

[2] C. Carathéodory, Theory of Functions of a Complex Variable, Vol.1, Chelsea Publishing Company, 1954.

[3] G. Ciobanu, Distributed Algorithms Over Communicating Membrane Systems, Bio Systems, 70(2):123–133, 2003.

[4] W. F. Doolittle, Uprooting the Tree of Life, Scientific American, 282(2):90–95, 2000.

[5] T. -O. Ishdorj, M. Ionescu, Replicative-Distribution Rules in P Systems with Active Membranes, Proceeding of the First International Colloquium on Theoretical Aspects of Computing (ICTAC 2004), 68–83, 2004.

[6] C. Li, Validating P System as Distributed Computing Models, Master thesis, 2008.

[7] C. Martín-Vide, G. Păun, J. Pazos, A. Rodríguez-Patón, Tissue P Systems, Theoretical Computer Science, 296(2):295–326, 2003.

[8] R. Nicolescu, M. J. Dinneen, Y.-B. Kim, Structured Modelling with Hyperdag P Systems: Part A, CDMTCS Research Report Series, CDMTCS-342, 1–24, December 2008.

[9] R. Nicolescu, M. J. Dinneen, Y.-B. Kim, Discovering the Membrane Topology of Hyperdag P Systems, Proceeding of the Tenth Workshop on Membrane Computing (WMC10 2009), Curtea de Arge¸s, Romania, August 24–27, 426–451, 2009.

[10] G. Păun, Computing with Membranes. Journal of Computer and System Sciences, 61(1):108–143, 2000, (and Turku Center for Computer Science, TUCS Report 208, November 1998).

[11] G. Păun, Membrane Computing: An Introduction. Springer-Verlag, 2002.

[12] G. Păun, Introduction to Membrane Computing, Proceeding of the First Brainstorming Workshop on Uncertainty in Membrane Computing, 17–65, 2004.

[13] G. Păun, R. A. Păun, Membrane Computing as a Framework for Modeling Economic Processes, Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2005), 11–18, 2005.

[14] M. Slikker, A. Van Den Nouweland, Social and Economic Networks in Cooperative Game Theory, Kluwer Academic Publishers, 2001.

[15] V. I. Voloshin, Coloring Mixed Hypergraphs: Theory, Algorithms and Applications, American Mathematical Society, 2002.

[16] C. Zandron, C. Ferretti, G. Mauri, Solving NP-Complete Problems Using P Systems with Active Membranes, Proceeding of the Second International Conference on Unconventional Models of Computation, 289–301, 2000.
How to Cite
DINNEEN, Michael J.; KIM, Yun-Bum; NICOLESCU, Radu. Towards Structured Modelling with Hyperdag P Systems. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 5, n. 2, p. 224-237, june 2010. ISSN 1841-9844. Available at: <>. Date accessed: 11 aug. 2020. doi:


hyperdag P systems, tissue and neural P systems, membrane structures