کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4608853 1338386 2010 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computational complexity of tissue-like P systems
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات آنالیز ریاضی
پیش نمایش صفحه اول مقاله
Computational complexity of tissue-like P systems
چکیده انگلیسی

Membrane systems, also called P systems, are biologically inspired theoretical models of distributed and parallel computing. This paper presents a new class of tissue-like P systems with cell separation, a feature which allows the generation of new workspace. We study the efficiency of the class of P systems and draw a conclusion that only tractable problems can be efficiently solved by using cell separation and communication rules with the length of at most 1. We further present an efficient (uniform) solution to SAT by using cell separation and communication rules with length at most 6. We conclude that a borderline between efficiency and non-efficiency exists in terms of the length of communication rules (assuming P≠NP). We discuss future research topics and open problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Complexity - Volume 26, Issue 3, June 2010, Pages 296–315
نویسندگان
, ,