Towards Structured Modelling with Hyperdag P Systems
Keywords:
hyperdag P systems, tissue and neural P systems, membrane structuresAbstract
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
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
