کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6865892 678089 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The power of time-free tissue P systems: Attacking NP-complete problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
The power of time-free tissue P systems: Attacking NP-complete problems
چکیده انگلیسی
Tissue P systems, which are inspired from the structures and functions of biological tissues, are a class of distributed and parallel computing models. In traditional tissue P systems, each rule (abstracted from biochemical reaction) has precise global execution time. The restriction on the execution time does not coincide with the biological fact, since the execution time of biochemical reaction can vary because of external uncontrollable conditions. In this work, we investigate a class of tissue P systems with no restriction on the execution time of each rule, named time-free tissue P systems. As a result, it is proved that the execution time of the rules has no influence on the computation results of the systems. Moreover, we consider the computational efficiency of time-free tissue P systems and prove that the Maximum Clique Problem and Hamilton Path Problem can be solved in this way in polynomial time with respect to the size of the problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Neurocomputing - Volume 159, 2 July 2015, Pages 151-156
نویسندگان
, , , , ,