Tissue P Systems with Look-ahead Mode

JIANG Yun; SONG Tao; ZHANG Zheng

Article Contents

Article Navigation > Chinese Journal of Electronics > 2014 > 23(1): 81-86

JIANG Yun, SONG Tao, ZHANG Zheng, “Tissue P Systems with Look-ahead Mode,” Chinese Journal of Electronics, vol. 23, no. 1, pp. 81-86, 2014,

Citation:

JIANG Yun, SONG Tao, ZHANG Zheng, “Tissue P Systems with Look-ahead Mode,” Chinese Journal of Electronics, vol. 23, no. 1, pp. 81-86, 2014,

JIANG Yun, SONG Tao, ZHANG Zheng, “Tissue P Systems with Look-ahead Mode,” Chinese Journal of Electronics, vol. 23, no. 1, pp. 81-86, 2014,

Citation:

JIANG Yun, SONG Tao, ZHANG Zheng, “Tissue P Systems with Look-ahead Mode,” Chinese Journal of Electronics, vol. 23, no. 1, pp. 81-86, 2014,

PDF( 185 KB)

Tissue P Systems with Look-ahead Mode

1.
School of Computer Science and Information Engineering, Chongqing Technology and Business University, Chongqing 400067, China;
2.
Image Processing and Intelligent Control Key Laboratory of Education Ministry of China, Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China

Funds: This work is supported by Youth Doctoral Foundation of Chongqing Technology and Business University (No.1152006).

Received Date: 2012-07-01
Rev Recd Date: 2013-01-01
Publish Date: 2014-01-05

Abstract

Abstract

Tissue P systems are a class of distributed and parallel computing models inspired from inter-cellular communication and cooperation between cells. In this work, a variant of tissue P system, named tissue P system with look-ahead mode, is discussed for decreasing the inherent non-determinism of tissue P systems and helping implementing tissue P systems on computers. Such systems are proved to be universal by simulating register machine, and they are also proved to be able to efficiently solve computationally hard problems by means of a spacetime tradeoff, which is illustrated with a polynomial solution to 3-coloring problem.
- Tissue P system,
- Look-ahead mode,
- Recursively enumerable language,
- Cell separation,
- 3-Coloring

FullText(HTML)

References(27)

References

Gh. Păun,"Computing with membranes", Journal of Computer and System Sciences, Vol.61, No.1, pp.108-143, 2000.

C. Martín-Vide, J. Pazos, Gh. Păun, et al.,"Tissue P systems", Theoretical Computer Science, Vol.296, No.2, pp.295-326, 2003.

M. Ionescu, Gh. Páun, T. Yokomori,"Spiking neural P systems", Fundamenta Informaticae, Vol.71, No.2-3, pp.279-308,2006.

L. Pan, Gh. Păun,"Spiking neural P systems with anti-spikes", International Journal of Computers, Communications & Control, Vol.IV, No.3, pp.273-284, 2009.

L. Pan, Gh. Păun,"Spiking neural P systems: An improved normal form", Theoretical Computer Science, Vol.411, No.6, pp.906-918, 2010.

L. Pan, X. Zeng,"Small universal spiking neural P systems working in exhaustive mode", IEEE Transactions on Nanobioscience, Vol.10, No.2, pp.99-105, 2011.

L. Pan, X. Zeng, X. Zhang,"Time-free spiking neural P systems", Neural Computation, Vol.23, No.5, pp.1320-1342, 2011.

K. Jiang, X. Shi,"Degree of spiking neural P systems without delay", Chinese Journal of Electronics, Vol.21, No.3, pp.419424, 2012.

L. Pan, M.J. Pérez-Jiménez,"Computational complexity of tissue-like P Systems", Journal of Complexity, Vol.26, No.3, pp.296-315, 2010.

T.O. Ishdorj, A. Leporati, L. Pan, et al.,"Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources", Theoretical Computer Science, Vol.411, No.25, pp.2345-2358, 2010.

X. Zhang, S. Wang, Y. Niu, L. Pan,"Tissue P systems with cell separation: Attacking the partition problem", Science China Information Sciences, Vol.54, No.2, pp.293-304, 2011.

L. Pan, D. Diaz-Pernil, M.J. Pérez-Jiménez,"Computation of Ramsey numbers by P systems with active membranes", International Journal of Foundations of Computer Science, Vol.22, No.1, pp.29-38, 2011.

Y. Niu, L. Pan, M.J. Pérez-Jiménez, M.R. Font,"A tissue P systems based uniform solution to tripartite matching problem", Fundamenta Informaticae, Vol.109, No.2, pp.179-188, 2011.

L. Pan, Gh. Păun, M.J. Pérez-Jiménez,"Spiking neural P systems with neuron division and budding", Science China Information Sciences, Vol.54, No.8, pp.1596-1607, 2011.

C. Lu, X. Shi,"Uniform solution to QSAT by P systems with proteins", Chinese Journal of Electronics, Vol.21, No.4, pp.667672, 2012.

G. Ciobanu, Gh. Păun, M.J. Pérez-Jiménez, Applications of Membrane Computing, Springer, 2006.

Gh. Păun, Membrane Computing: An Introduction, Berlin, Germany: Springer-Verlag, 2002.

P systems web page htt: //ppage.psystems.eu/.

S. Singer, G. Nicolson,"The fluid mosaic model of the structure of cell membranes", Science, Vol.175, No.4023, pp.720-731, 1972.

A. Alhazov, R. Freund, M. Oswald,"Tissue P systems with antiport rules and small numbers of symbols and cells", Lecture Notes in Computer Science, Vol.3572, pp.54-78, 2005.

Gh. Păun, M.J. Pérez-Jiménez, A. Riscos-Nú ñez,"Tissue P system with cell division", International Journal of Computers, Communications and Control, Vol.3, No.3, pp.295-303, 2008.

R. Freund,"Sequential P systems", Romanian Journal of Information Science and Technology, Vol.4, No.1-2, pp.77-88, 2001.

F. Bernardini, F.J. Romero-Campero, M. Gheorghe, et al.,"An P systems with bounded parallelism", In Proc. 7th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pp.399-406, 2005.

G. Ciobanu, L. Pan, Gh. Păun, M.J. Pérez-Jiménez,"P systems with minimal parallelism", Theoretical Computer Science, Vol.378, No.1. pp.117-130, 2007.

S. Verlan,"Look-ahead evolution for P systems", Lecture Notes in Computer Science, Vol.5957, pp.479-485, 2010.

J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, MA, 1979.

C. Martín-Vide, J. Pazos, Gh. Păun, A. Rodríguez-Patón,"A new class of symbolic abstract neural nets: Tissue P systems", Lecture Notes in Computer Science, Vol.2387, pp.290299, 2002.

Relative Articles

Supplements(0)

Cited By

Proportional views