(Tissue) P Systems with Unit Rules and Energy Assigned to Membranes

• Autorzy: Alhazov A. , Freund R. , Leporati A. , Oswald M. , Zandron C.
• Języki publikacji: EN

Abstrakty

EN

We introduce a new variant of membrane systems where the rules are directly assigned to membranes and, moreover, every membrane carries an energy value that can be changed during a computation by objects passing through the membrane. The result of a successful computation is considered to be the distribution of energy values carried by the membranes. We show that for systems working in the sequential mode with a kind of priority relation on the rules we already obtain universal computational power. When omitting the priority relation, we obtain a characterization of the family of Parikh sets of languages generated by context-free matrix grammars. On the other hand, when using the maximally parallel mode, we do not need a priority relation to obtain computational completeness. Finally, we introduce the corresponding model of tissue P systems with energy assigned to the membrane of each cell and objects moving from one cell to another one in the environment as well as being able to change the energy of a cell when entering or leaving the cell. In each derivation step, only one object may pass through the membrane of each cell. When using priorities on the rules in the sequential mode (where in each derivation step only one cell is affected) as well as without priorities in the maximally parallel mode (where in each derivation step all cells possible are affected) we again obtain computational completeness, whereas without priorities on the rules in the sequential mode we only get a characterization of the family of Parikh sets of languages generated by context-free matrix grammars.

Słowa kluczowe

EN

computational completeness; matrix grammars; membrane computing; P systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 4
• Strony: 391--408
• Opis fizyczny: bibliogr. 18 poz.

Twórcy

autor

Alhazov A.

autor

Freund R.

autor

Leporati A.

autor

Oswald M.

autor

Zandron C.

• Faculty of Informatics, Vienna University of Technology, Austria,

Bibliografia

• [1] Dassow, J., Pǎun, Gh.: Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin, 1989.
• [2] Freund, R.: Generalized P-systems, in: G. Ciobanu, Gh. P˘aun (Eds.), Proceedings Fundamentals of Computation Theory, Lecture Notes in Computer Science 1684, Springer-Verlag, Berlin, 1999, 281-292.
• [3] Freund, R.: Sequential P-systems, Romanian Journal of Information Science and Technology 4, 1-2, 2001, 77-88.
• [4] Freund, R.: Energy-controlled P systems, in: Gh. P˘aun, G. Rozenberg, A. Salomaa, C. Zandron (Eds.), Membrane Computing. InternationalWorkshop, WMC-CdeA 2002, Curtea de Arges¸, Romania, August 2002, Lecture Notes in Computer Science 2597, Springer-Verlag, Berlin, 2003, 247-260.
• [5] Freund, R., Leporati, A., Oswald, M., Zandron, C.: Sequential P systems with unit rules and energy assigned to membranes, in: M. Margenstern (Ed.), Machines, Computations, and Universality: 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers, Lecture Notes in Computer Science 3354, Springer-Verlag, Berlin, 2005, 200-210.
• [6] Freund, R., Oswald, M.: GP Systems with forbidding context, Fundamenta Informaticae 49, 1-3, 2002, 81-102.
• [7] Freund, R., Oswald, M.: P systems with conditional communication rules assigned to membranes, to appear in JALC.
• [8] Freund, R., Pǎun, Gh.: On the number of non-terminals in graph-controlled, programmed, and matrix grammars, in: M. Margenstern, Y. Rogozhin (Eds.), Universal Machines and Computations, Chis¸in˘au, 2001, Lecture Notes in Computer Science 2055, Springer-Verlag, Berlin, 2001, 214-225.
• [9] Freund, R., Pǎun, Gh.: From regulated rewriting to computing with membranes: collapsing hierarchies, Theoretical Computer Science 312, 2004, 143-188.
• [10] Freund, R., Pǎun, Gh., Pérez-Jiménez, M.J.: Tissue-like P systems with channel states, in [15], 206-223 and Theoretical Computer Science 330, 1, 2005, 101-116.
• [11] Leporati, A., Mauri, G., Zandron, C.: Simulating the Fredkin gate with energy-based P systems, in [15], 292-308.
• [12] Minsky,M. L.: Computation. Finite and Infinite Machines, Prentice Hall, Englewood Cliffs, New Jersey, 1967.
• [13] Pǎun, Gh.: Computing with membranes, Journal of Computer and System Sciences 61, 1, 2000, 108-143 and TUCS Research Report 208, 1998 (http://www.tucs.fi).
• [14] Pǎun, Gh.: Membrane Computing: an Introduction, Springer-Verlag, Berlin, 2002.
• [15] Gh. Pǎun, A. Riscos-Nuñez, A. Romero-Jiménez, F. Sancho-Caparrini (Eds.), Second BrainstormingWeek on Membrane Computing, Sevilla, Spain, Feb. 2-7, 2004, Dept. of Computer Sciences and Artificial Intelligence, Univ. of Sevilla Tech. Report 01/2004.
• [16] Pǎun, Gh., Suzuki, Y., Tanaka, H.: P Systems with energy accounting, Int. J. Computer Math. 78, 3, 2001, 343-364.
• [17] Rozenberg, G., Salomaa, A. (Eds.): Handbook of Formal Languages, Springer-Verlag, Berlin, 1997.
• [18] The P Systems Web Page, http://psystems.disco.unimib.it