Towards Structured Modelling with Hyperdag P Systems

Authors

  • 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

Keywords:

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

Abstract

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.

References

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

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

G. Ciobanu, Distributed Algorithms Over Communicating Membrane Systems, Bio Systems, 70(2):123-133, 2003. http://dx.doi.org/10.1016/S0303-2647(03)00035-2

W. F. Doolittle, Uprooting the Tree of Life, Scientific American, 282(2):90-95, 2000. http://dx.doi.org/10.1038/scientificamerican0200-90

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.

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

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. http://dx.doi.org/10.1016/S0304-3975(02)00659-X

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. http://www.cs.auckland.ac.nz/CDMTCS/researchreports/342hyperdagA.pdf

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.

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).

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

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

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.

M. Slikker, A. Van Den Nouweland, Social and Economic Networks in Cooperative Game Theory, Kluwer Academic Publishers, 2001. http://dx.doi.org/10.1007/978-1-4615-1569-2

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

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.

Published

2010-06-01

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.