Tissue P systems. (English) Zbl 1045.68063
Summary: Starting from the way the inter-cellular communication takes place by means of protein channels (and also from the standard knowledge about neuron functioning), we propose a computing model called a tissue \(P\) system, which processes symbols in a multiset rewriting sense, in a net of cells. Each cell has a finite state memory, processes multisets of symbol-impulses, and can send impulses (”excitations”) to the neighboring cells. Such cell nets are shown to be rather powerful: they can simulate a Turing machine even when using a small number of cells, each of them having a small number of states. Moreover, in the case when each cell works in the maximal manner and it can excite all the cells to which it can send impulses, then one can easily solve the Hamiltonian Path Problem in linear time. A new characterization of the Parikh images of ET0L languages is also obtained in this framework. Besides such basic results, the paper provides a series of suggestions for further research.
MSC:
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
Keywords:
Natural computing; Membrane computing; P systems; Chomsky hierarchy; Lindenmayer hierarchy; NP-complete problemsReferences:
| [1] | Alberts, B., Essential Cell Biology. An Introduction to the Molecular Biology of the Cell (1998), Garland Publ. Inc: Garland Publ. Inc New York, London |
| [2] | Arbib, M. A., Brains, Machines, and Mathematics (1987), Springer: Springer Berlin · Zbl 0174.02401 |
| [3] | Arbib, M. A., The Metaphorical BrainAn Introduction to Schemes and Brain Theory (1988), Wiley Interscience: Wiley Interscience Berlin |
| [4] | Banatre, J. P.; Fradet, P.; LeMetayer, D., Gamma and the chemical abstract reaction modelfifteen years after, (Calude, C. S.; Păun, Gh.; Rozenberg, G.; Salomaa, A., Multiset Processing. Mathematical, Computer Science, and Molecular Computing Points of View, Lecture Notes in Computer Science, Vol. 2235 (2001), Springer: Springer Berlin), 17-44 · Zbl 1052.68037 |
| [5] | Blank, D. S., Connectionist symbol processingdead or alive?, Neural Comput. Surveys, 2, 1-40 (1999) |
| [6] | Calude, C.; Marcus, S.; Păun, Gh., The universal grammar as a hypothetical brain, Rev. Roum. Ling., 24, 5, 479-489 (1979) · Zbl 0457.68093 |
| [7] | Calude, C.; Păun, Gh., Computing with Cells and Atoms (2000), Taylor and Francis: Taylor and Francis London |
| [8] | (Choffrut, C., Automata Networks, Lecture Notes in Computer Science, Vol. 316 (1988), Springer: Springer Berlin) · Zbl 0639.00041 |
| [9] | Csuhaj-Varju, E., Networks of language processors, (Păun, Gh.; Rozenberg, G.; Salomaa, A., Current Trends in Computer Science (2001), World Sci.: World Sci. Singapore), 781-800 · Zbl 1049.68597 |
| [10] | Csuhaj-Varju, E.; Dassow, J.; Kelemen, J.; Păun, Gh., Grammar Systems. A Grammatical Approach to Distribution and Cooperation (1994), Gordon and Breach: Gordon and Breach London · Zbl 0925.68286 |
| [11] | Csuhaj-Varju, E.; Martin-Vide, C.; Mitrana, V., Multiset automata, (Calude, C. S.; Păun, Gh.; Rozenberg, G.; Salomaa, A., Multiset Processing. Mathematical, Computer Science, and Molecular Computing Points of View, Lecture Notes in Computer Science, Vol. 2235 (2001), Springer: Springer Berlin), 67-82 · Zbl 1052.68071 |
| [12] | Culik II, K.; Salomaa, A.; Wood, D., Systolic tree acceptors, RAIRO, 18, 53-79 (1984) · Zbl 0571.68043 |
| [13] | Dassow, J.; Păun, Gh., Regulated Rewriting in Formal Language Theory (1989), Springer: Springer Berlin |
| [14] | Esik, Z., A note on isomorphic simulation of automata by networks of two-state automata, Discrete Applied Math., 30, 77-82 (1991) · Zbl 0737.05052 |
| [15] | R. Freund, Gh. Păun, On the number of non-terminals in graph-controlled, programmed, and matrix grammars, Proc. of the MCU Conf., Chişinău, 2001, Lecture Notes in Computer Science, Vol. 2055, Springer, Berlin, 2001, 214-225.; R. Freund, Gh. Păun, On the number of non-terminals in graph-controlled, programmed, and matrix grammars, Proc. of the MCU Conf., Chişinău, 2001, Lecture Notes in Computer Science, Vol. 2055, Springer, Berlin, 2001, 214-225. · Zbl 0984.68091 |
| [16] | Gecseg, F., Products of Automata (1986), Springer: Springer Berlin · Zbl 0636.68058 |
| [17] | Hauschild, D.; Jantzen, M., Petri nets algorithms in the theory of matrix grammars, Acta Informatica, 31, 719-728 (1994) · Zbl 0834.68064 |
| [18] | S.C. Kleene, Representation of events in nerve nets and finite automata, Automata Studies, Princeton Univ. Press, Princeton, N.J., 1956, 2-42.; S.C. Kleene, Representation of events in nerve nets and finite automata, Automata Studies, Princeton Univ. Press, Princeton, N.J., 1956, 2-42. |
| [19] | M. Kudlek, C. Martin-Vide, Gh. Păun, Toward FMT (Formal Macroset Theory), Pre-proc. of Workshop on Multiset Processing, Curtea de Argeş, Romania, TR 140, CDMTCS, Univ. Auckland, 2000, pp. 149-158.; M. Kudlek, C. Martin-Vide, Gh. Păun, Toward FMT (Formal Macroset Theory), Pre-proc. of Workshop on Multiset Processing, Curtea de Argeş, Romania, TR 140, CDMTCS, Univ. Auckland, 2000, pp. 149-158. |
| [20] | Loewenstein, W. R., The Touchstone of Life. Molecular Information, Cell Communication, and the Foundations of Life (1999), Oxford Univ. Press: Oxford Univ. Press New York, Oxford |
| [21] | Mateescu, A.; Mitrana, V., Parallel finite automata systems communicating by states, Intern. J. Found. Computer Sci., 13, 733-749 (2002) · Zbl 1066.68069 |
| [22] | McCulloch, W. S.; Pitts, W. H., A logical calculus of the ideas immanent in nervous activity, Bull. Math. Biophys., 5, 115-133 (1943) · Zbl 0063.03860 |
| [23] | Minsky, M., ComputationFinite and Infinite Machines (1967), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0195.02402 |
| [24] | Ch.P. Papadimitriou, Computational Complexity, Reading, MA, 1994.; Ch.P. Papadimitriou, Computational Complexity, Reading, MA, 1994. · Zbl 0833.68049 |
| [25] | Gh. Păun, Computing with membranes, J. Computer Syst. Sci. 61(1) (2000) 108-143; see also Turku Center for Computer Science-TUCS Report No. 208, 1998, www.tucs.fi; Gh. Păun, Computing with membranes, J. Computer Syst. Sci. 61(1) (2000) 108-143; see also Turku Center for Computer Science-TUCS Report No. 208, 1998, www.tucs.fi · Zbl 0956.68055 |
| [26] | Gh. Păun, Y. Sakakibara, T. Yokomori, P systems on graphs of restricted forms, Publicationes Math. Debrecen, to appear.; Gh. Păun, Y. Sakakibara, T. Yokomori, P systems on graphs of restricted forms, Publicationes Math. Debrecen, to appear. · Zbl 1006.68048 |
| [27] | Rozenberg, G.; Salomaa, A., The Mathematical Theory of L Systems (1980), Academic Press: Academic Press New York · Zbl 0365.68072 |
| [28] | (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, 3 volumes (1997), Springer: Springer Berlin) · Zbl 0866.68057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
