Multiset-Based Self-Assembly of Graphs

• Autorzy: Bernardini F. , Brijder R. , Rozenberg G. , Zandron C.
• Języki publikacji: EN

Abstrakty

EN

We present a model for self-assembly of graphs based on multisets and the formalism of membrane systems. The model deals with aggregates of cells which are defined as undirected graphs where a multiset over a fixed alphabet is assigned to each vertex. The evolution of these aggregates is determined by an application of multiset-based aggregation rules to enlarge the current structure as well as an application of membrane-systems-based communication rules to enable cells to exchange objects alongside the edges of the graph. We compare the generative power of self-assembly membrane systems with and without communication rules, and we characterise properties of the sets of graphs generated by these systems. We also introduce two notions of stability for self-assembly processes that capture the idea of having produced a stable structure. Finally, we investigate self-assembly membrane systems where the alphabet is a singleton.

Słowa kluczowe

EN

multisets; membrane system; self-assembly; graph generation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 75, nr 1-4
• Strony: 49--75
• Opis fizyczny: bibliogr. 21 poz., wykr.

Twórcy

autor

Bernardini F.

autor

Brijder R.

autor

Rozenberg G.

autor

Zandron C.

• LIACS, Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands,

Bibliografia

• [1] The P Systems Web Page, http://psystems.disco.unimib.it.
• [2] Abelson, H., Allen, D., Coore, D., Hanson, C., Homsy, G., Knight, F., Nagpal, R., Rauch, E., Sussman, J. G., Weiss, R.: Amorphous Computing, Comm. of ACM, 43, 2002, 74-82.
• [3] Ben-Jacob, E., Levine, H.: Self-Engineering Capabilities of Bacteria, Journal of Royal Society Interface, 3(6), 2006, 197-21.
• [4] Bernardini, F., Gheorghe, M.: Population P Systems, Journal of Universal Computer Science, 10(5), May 2004, 509-539.
• [5] Bernardini, F., Gheorghe, M., Krasnogor, N., Giavitto, J. L.: On Self-Assembly in Population P Systems, in: Unconventional Computation. 4th International Conference, UC 2005, Sevilla, Spain, October 2005, Proceedings (C. Calude, M. Dinneen, G. Pǎun, M. J. Pérez-Jiménez, G. Rozenberg, Eds.), vol. 3365 of Lecture Notes in Computer Science, Springer, 2005, 46-57.
• [6] Bollobá, B.: Modern Graph Theory, Graduate Texts in Mathematics, Springer, Berlin, 1998.
• [7] Chen, J., Jonoska, N., Rozenberg, G., Eds.: Nanotechnology: Science and Computation, Natural Computing Series, Springer, 2006.
• [8] Drexler, K. E.: Nanosystems: Molecular Machinery, Manufacturing and Computation, Wiley-Interscience, 1992.
• [9] Franco, G., Jonoska, N.: Forbidding-Enforcing Conditions in DNA Self-assembly of Graphs, in: Nanotechnology: Science and Computation (J. Chen, N. Jonoska, G. Rozenberg, Eds.), Natural Computing, Springer, 2006, 105-120.
• [10] Gheorghe, M., P˘aun, G.: Computing by Self-Assembly: DNAMolecules, Polynominoes, Cells, in: Systems Self-Assembly: Multidisciplinary Snapshots (N. Krasnogor, S. Gustafson, D. Pelta, J. L. Verdegay, Eds.), Studies in Multidisciplinarity, Elsevier, 2006, In press.
• [11] Jonoska, N., McColm, G. L.: A Computational Model for Self-Assembling Flexible Tiles, in: Unconventional Computation. 4th International Conference, UC 2005, Sevilla, Spain, October 2005, Proceedings (C. Calude, M. Dinneen, G. P˘aun, M. J. Pérez-Jiménez, G. Rozenberg, Eds.), vol. 3365 of Lecture Notes in Computer Science, Springer, 2005, 142-156.
• [12] Klavins, E., Ghrist, R., Lipsky, D.: A Grammatical Approach to Self-Organizing Robotic Systems, 2006, To appear in IEEE Transactions on Automatic Control.
• [13] Krasnogor, N., Gustafson, S.: A Family of Conceptual Problems in the Automated Design of Systems Self-Assembly, in: Proc. Second International Conference on the Foundations of Nanoscience: Self-Assembled Architectures and Devices, 2005, 31-35.
• [14] Pǎun, G.: Computing with Membranes, Journal of Computer and System Sciences, 61(1), 2000, 108-143.
• [15] Pǎun, G.: Membrane Computing. An Introduction, Springer, Berlin, 2002.
• [16] Rothemund, P.W. K.,Winfree, E.: The Program-Size Complexity of Self-Assembled Squares, in: Proceedings of the Thirty-Second ACM Symposium on Theory of Computing, ACM Press, 2000, 459-468.
• [17] Rozenberg, G., Salomaa, A., Eds.: Handbook of Formal Languages, vol. 1-3, Springer, 1997.
• [18] Sha, R., Zhang, X., Liao, S., Constantinou, P. E., Ding, B., Wang, T., Garibotti, A. V., Zhong, H., Israel, L. B., Wang, X., Wu, G., Chakraborty, B., Chen, J., Zhang, Y., Yan, H., Shen, Z., Shen, W., Sa-Ardyen, P., Kopatsch, J., Zheng, J., Lukeman, P. S., Sherman, W. B., Mao, C., Jonoska, N., Seeman, N. C.: Structural DNA Nanotechnology: Molecular Construction and Computation, in: Unconventional Computation. 4th International Conference, UC 2005, Sevilla, Spain, October 2005, Proceedings (C. Calude, M. Dinneen, G. Pǎun, M. J. Pérez-Jiménez, G. Rozenberg, Eds.), vol. 3365 of Lecture Notes in Computer Science, Springer, 2005, 20-31.
• [19] Whitesides, G. M., Grzybowski, B.: Self-Assembly at All Scales, Science, 295, 2002, 2418-2421.
• [20] Winfree, E.: Algorithmic Self-Assembly of DNA, Ph.D. Thesis, California Institute of Technology, USA, 1998.
• [21] Winfree, E., Liu, F., Wenzler, L. A., Seeman, N. C.: Design and Self-Assembly of Two Dimensional DNA Crystals, Nature, 394, 1998, 539-544.