<p>In this paper, we introduce a new method of filtering strings before communication in networks of evolutionary processors which is based on whether the length of strings at the given node increases, decreases, or remains unchanged after an evolutionary step is performed. This filtering mechanism differs from the usual ones, where context conditions are considered, as it is based only on quantitative conditions (the lengths of the strings) and does not take into account qualitative properties of the string to be communicated. We prove that any recursively enumerable language can be obtained as the language of a variant of hybrid networks of evolutionary processors with this new communication mode. We also show how two well-known NP-complete problems can be solved by the new model in linear time.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Length-driven communication in networks of evolutionary processors

  • Erzsébet Csuhaj-Varjú,
  • Pramod Kumar Sethy

摘要

In this paper, we introduce a new method of filtering strings before communication in networks of evolutionary processors which is based on whether the length of strings at the given node increases, decreases, or remains unchanged after an evolutionary step is performed. This filtering mechanism differs from the usual ones, where context conditions are considered, as it is based only on quantitative conditions (the lengths of the strings) and does not take into account qualitative properties of the string to be communicated. We prove that any recursively enumerable language can be obtained as the language of a variant of hybrid networks of evolutionary processors with this new communication mode. We also show how two well-known NP-complete problems can be solved by the new model in linear time.