Editing Configurations of P Systems

• Autorzy: Csuhaj-Varjú E. , Di Nola Di , Paun G. , Pérez-Jiménez M.J. , Vaszil G.
• Języki publikacji: EN

Abstrakty

EN

This paper proposes and investigates the possibility of transforming a configuration of a P system (the membrane structure and the multisets of symbol-objects present in the compartments) into another configuration by means of a given set of rules to be applied to the membranes and to the multisets of objects. Although this transformation is obtained during the computation in a P system, we consider it as a goal per se, as a pre-computation phase, when the system itself is built. In this framework, several important problems appear: the edit-distance between configurations (with respect to a given set of editing rules), normal forms, the reachability of configurations, or the existence of single configurations from which a given family of configurations can be constructed, only to mention a few. We investigate here some of these questions; the paper is mainly devoted to formulating problems in the new framework, to calling attention to the possible extensions and the usefulness of the present approach.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 82, nr 1-2
• Strony: 29--46
• Opis fizyczny: bibliogr. 16 poz., tab., wykr.

Twórcy

autor

Csuhaj-Varjú E.

autor

Di Nola Di

autor

Paun G.

autor

Pérez-Jiménez M.J.

autor

Vaszil G.

• Computer and Automation Research Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111 Budapest, Hungary,

Bibliografia

• [1] Alhazov, A., Ishdorj, T. O.: Membrane operations in P systems with active membranes, Proc. Second Brainstorming Week on Membrane Computing, TR 01/04 of Research Group on Natural Computing, Sevilla University, Sevilla, 2004, 37-44.
• [2] Alhazov, A., Pan, L., P˘aun, G.: Trading polarizations for labels in P systems with active membranes, Acta Informatica, 41(2-3), 2005, 111-144.
• [3] Bel Enguix, G., Jim´enez-Lopez, M. D.: Linguistic membrane systems and applications, in: Applications of Membrane Computing (G. Ciobanu, G. P˘aun, M. J. Pérez-Jiménez, Eds.), Springer-Verlag, 2005, 347-388.
• [4] Calude, C., P˘aun, G.: Bio-steps beyond Turing, BioSystems, 77, 2004, 175-194.
• [5] Cardelli, L.: Brane calculi. Interactions of biological membranes, in: Computational Methods in Systems Biology (V. Danos, V. Schachter, Eds.), vol. 3082 of Lecture Notes in Computer Science, Springer-Verlag, 2005, 257-280.
• [6] Cordón-Franco, A., Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., Riscos-Núñez, A.: Weak metrics on configurations of a P system, Proc. Second Brainstorming Week on Membrane Computing, TR 01/04 of Research Group on Natural Computing, Sevilla University, Sevilla, 2004, 139-151.
• [7] Freund, R., Kari, L., Oswald, M., Sos´ık, P.: Computationally universal P systems without priorities: two catalysts are sufficient, Theoretical Computer Science, 330(2), 2005, 251-266.
• [8] Ginsburg, S.: Algebraic and Automata-Theoretic Properties of Formal Languages, North-Holland, Amsterdam, 1975.
• [9] Ibarra, O. H.: On the computational complexity of membrane computing systems, Theoretical Computer Science, 320(1), 2004, 98-109.
• [10] Ibarra, O. H., Dang, Z., Egecioglu, O.: Catalytic membrane systems, semilinear sets, and vector addition systems, Theoretical Computer Science, 312(2-3), 2004, 378-400.
• [11] Krishna, S. N., P˘aun, G.: P systems with mobile membranes, Natural Computing, 4(3), 2005, 255-274.
• [12] Minsky,M.: Computation. Finite and Infinite Machines, Prentice Hall, Englewood Cliffs, NJ, 1967.
• [13] Nilsoon, N. J.: Artificial Intelligence. A New Synthesis, The Morgan Kaufmann Series in Artificial Intelligence, San Francisco, 1998.
• [14] Păun, G.: Computing with membranes, Journal of Computer and System Sciences, 61, 2000, 108-143.
• [15] Păun, G.: Membrane Computing. An Introduction, Springer-Verlag, Berlin, 2002.
• [16] Pérez-Jiménez, M. J., Romero-Jiménez, A., Sancho-Caparrini, F.: Teoria de la Complejidad en Modelos de Computatión Celular con Membranas, Editorial Kronos, Sevilla, 2002.