کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10334315 690377 2005 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the size complexity of hybrid networks of evolutionary processors
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the size complexity of hybrid networks of evolutionary processors
چکیده انگلیسی
The goal of this paper is twofold. Firstly, to survey in a systematic and uniform way the main results regarding the size descriptional complexity measures of hybrid networks of evolutionary processors as generating devices. Secondly, we improve some results about a size measure, prove that it is connected, and discuss the possibility of computing this measure for regular and context-free languages. We also briefly present a few NP-complete problems and recall how they can be solved in linear time by accepting networks of evolutionary processors with linearly bounded resources (nodes, rules, symbols). Finally, the size complexity of accepting hybrid networks of evolutionary processors recognizing all NP languages in polynomial time is briefly discussed.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 330, Issue 2, 2 February 2005, Pages 205-220
نویسندگان
, , ,