The Topological Structures of Membrane Computing

• Autorzy: Giavitto J-L. , Michel O.
• Języki publikacji: EN

Abstrakty

EN

In its initial presentation, the P system formalism describes the topology of the membranes as a set of nested regions. In this paper, we present an algebraic structure developped in combinatorial topology that can be used to describe finer adjacency relationships between membranes. Using an appropriate abstract setting, this technical device enables us to reformulate also the computation within a membrane and proposes a unified view on several computational mechanisms initially inspired by biological processes. These theoretical tools are instantiated in MGS, an experimental programming language handling various types of membrane structures in a homogeneous and uniform syntax.

Słowa kluczowe

EN

membrane computing; gamma; CHAM; P systems; L system; cellular automata; group based fields; rewriting; topological collection; declarative programming language

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 49, nr 1-3
• Strony: 123--145
• Opis fizyczny: Bibliogr. 26 poz., wykr.

Twórcy

autor

Giavitto J-L.

autor

Michel O.

• LaMI, umr 8042 CNRS - University of Evry, Tour Evry 2, 523 Place des terasses de l'Agora, 91000 Evry, France,

Bibliografia

• [1] Banatre, J. P, Metayer, D. L.: A new computational model and its discipline of programming. Technical Report RR-0566, Inria, 1986.
• [2] Blelloch, G.: NESL: A nested data-parallel language (version 2.6), Technical Report CMU-CS-93-129, School of Computer Science, Carnegie Mellon University, April 1993.
• [3] Buneman, P, Naqvi, S., Tannen, V., Wong, L.: Principles of programming with complex objects and collection types. Theoretical Computer Science, 149(1), 18 September 1995, 3-48.
• [4] Fisher, M„ Malcolm, G., Paton, R.: Spatiological processes in intracellular signalling, BioSystems, 55, 2000, 83-92.
• [5] Fontana, W.: Algorithmic Chemistry. Proceedings of the Workshop on Artificial Life (ALIEE ’90) (C. G. Langton, C. Taylor, J. D. Farmer, S. Rasmussen, Eds.), 5, Addison-Wesley, Redwood City, CA, USA, February 1992, ISBN 0-201-52570-4.
• [6] Fontana, W., Buss, L.: ’'The Arrival of the Fittest”: Toward a Theory of Biological Organization, Bulletin of Mathematical Biology, 1994.
• [7] Fontana, W., Buss, L.: Boundaries and Barriers, Casti, J. and Karlqvist, A. edts„ chapter The barrier of objects: from dynamical systems to bounded organizations, Addison-Wesley, 1996, 56-1 16.
• [8] Giavitto, J.-L.: A framework for the recursive definition of data structures., Proceedings of the 2nd International ACM SIG PIAN Conference on Principles and Practice of Declarative Programming (PPDP-00), ACM Press, September 20-23 2000.
• [9] Giavitto, J.-L., Michel, O.: Declarative definition of group indexed data structures and approximation of their domains., Proceedings of the 3nd Imternational ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP-01), ACM Press, September 2001.
• [10] Giavitto, J.-L., Michel, O.: MGS: a Rule-Based Programming Language for Complex Objects and Collec¬tions, Electronic Notes in Theoretical Computer Science (M. van den Brand, R. Verma, Eds.), 59, Elsevier Science Publishers, 2001.
• [11] Giavitto, J.-L., Michel, O.: MGS: a Programming Language for the Transformations of Topological Collections, Technical Report 61-2001, LaMI - Universitd d ’Evry Val d’Essonne, May 2001.
• [12] Giavitto, J.-L., Michel, O., Sansonnet, J.: Group-Based Fields, Parallel Symbolic Languages and Systems (Int. Workshop PSLS’95), LNCS 1068, Springer, 1996.
• [13] Henle, M.: A combinatorial introduction to topology, Dover publications, New-York, 1994.
• [14] Hoogcndijk, P. R, Backhouse, R. C.: Relational Programming Laws in the Tree, List, Bag, Set Hierarchy, Science of Computer Programming, 22(1-2), April 1994, 67-105.
• [15] Lienhardt, P: Topological models for boundary representation : a comparison with n-dimensional general¬ized maps, Computer-Aided Design, 23(1), 1991, 59-82.
• [16] Manca, V.: Logical string rewriting. Theoretical Computer Science, 264, 2 001,2 5-5 1.
• [17] Munkres, J.: Elements of Algebraic Topology, Addison-Wesley, 1984.
• [18] Norris , V., Fralick , J., Danchin, A.: A SeqA hyperstructure and its interactions direct the replication and sequestration of D NA , Molecular Microbiology, 37, 2000,69 6-702.
• [19] Palmer, R. S., Shapiro, V.: Chain Models of Physical Behavior for Engineering Analysis and Design, Research in Engineering Design, 5, 1993, 161-184, Springer International.
• [20] Paun, G.: Computing with Membranes: An Introduction, Bulletin of the European Association for Theoretical Computer Science, 67, February 1999, 139-152.
• [21] Paun, G.: From Cells to Computers: Computing with Membranes (P systems), Biosystems, 59(3), March 2001, 139-158.
• [22] Paun, G., Sakakibara, Y., Yokomori, T.: P Systems on Graphs of Restricted Forms, Publ. Math. Debrecen, 2001, (to appear).
• [23 ] Rozenberg, G., Salomaa, A.: Lindenmayer Systems, Springer, Berlin, 1992.
• [24 ] Tonti, E.: The algebraic-topological structure of physical theories. Symmetry, similarity and group theoretic methods in mechanics (P. G. Glockner, M. C. Sing, Eds.), Calgary, Canada, August 1974.
• [25] Tonti, E.: The reason for analogies between physical theories, Appl. Math. Modelling , 1, June 1976, 37-50.
• [26] Von Neumann, J.: Theory of Self-Reproducing Automata, Univ. of Illinois Press, 1966.