JUCS - Journal of Universal Computer Science 10(9): 1250-1271, doi: 10.3217/jucs-010-09-1250
Rewriting Tissue P Systems
Madhu 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
Corresponding author: Madhu Mutyam © Madhu Mutyam, Vaka Prakash, Kamala Krithivasan. This article is freely available under the J.UCS Open Content License. Citation:
Mutyam M, Prakash VJ, Krithivasan K (2004) Rewriting Tissue P Systems. JUCS - Journal of Universal Computer Science 10(9): 1250-1271. https://doi.org/10.3217/jucs-010-09-1250 |  |
Abstract
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.
Keywords
Tissue P systems, rewriting tissue P systems, computational universality, matrix grammars