Rewriting Tissue P Systems

Madhu Mutyam (International Institute of Information Technology, India)

Vaka Jaya Prakash (Department of Computer Science and Engineering, Indian Institute of Technology Madras, India)

Kamala Krithivasan (Department of Computer Science and Engineering, Indian Institute of Technology Madras, India)

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, computational universality, matrix grammars, rewriting tissue P systems

Categories: F.4.2, F.4.3