JUCS - Journal of Universal Computer Science 10(9): 1250-1271, doi: 10.3217/jucs-010-09-1250
Rewriting Tissue P Systems
expand article infoMadhu Mutyam, Vaka Jaya Prakash§, Kamala Krithivasan§
‡ International Institute of Information Technology, Hyderabad, India§ Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai, India
Open Access
By considering string-objects and rewriting rules, we propose a variant of tissue P systems, namely, rewriting tissue P systems. We show the computational efficiency of rewriting tissue P systems by solving the Satisfiability and the Hamiltonian path problems in linear time. We study the computational capacity of rewriting tissue P systems and show that rewriting tissue P systems with at most two cells and four states are computationally universal. We also show the universality result of rewriting tissue P systems with at most one cell and five states. Finally we propose some new directions for future work.
Tissue P systems, rewriting tissue P systems, computational universality, matrix grammars