Complete Obligatory Hybrid Networks of Evolutionary Processors

摘要

We consider obligatory hybrid networks of evolutionary processors (OHNEPs) introduced recently. It is a variant of hybrid network of evolutionary processors (HNEPs), differing from the main model as follows: in OHNEP a node discards the strings to which no operations are applicable, and underlying graph is directed. In this paper we consider OHNEPs with complete underlying graph. We show that such networks are computationally complete even using very simple evo-lutionary processors: one operation per node (obligatory left deletion, right insertion and obligatory substitution). In our proof, the total power of input/output filters does not exceed 3 symbols.