期刊
THEORETICAL COMPUTER SCIENCE
卷 296, 期 2, 页码 295-326出版社
ELSEVIER
DOI: 10.1016/S0304-3975(02)00659-X
关键词
natural computing; membrane computing; P systems; Chomsky hierarchy; Lindenmayer hierarchy; NP-complete problems
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. (C) 2002 Elsevier Science B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据