Length-driven communication in networks of evolutionary processors

Abstract 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.