کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6865892 | 678089 | 2015 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The power of time-free tissue P systems: Attacking NP-complete problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله 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](/preview/png/6865892.png)
چکیده انگلیسی
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
Journal: Neurocomputing - Volume 159, 2 July 2015, Pages 151-156
نویسندگان
Xiangrong Liu, Juan Suo, Stephen C.H. Leung, Juan Liu, Xiangxiang Zeng,