Dassow, Jürgen, Manea, Florin and Truthe, Bianca (2012) Networks of evolutionary processors: computationally complete normal forms. Natural Computing, 11 (4). pp. 595-607. DOI 10.1007/s11047-012-9331-z.

Preview

Text DasManTruNaCoRev.pdf Download (381kB) | Preview

Abstract

Networks of evolutionary processors (NEPs, for short) form a bio-inspired language generating computational model that was shown to be equivalent to the model of phrase-structure grammars. In this paper, we analyse different restricted variants of NEPs that preserve the computational power of the general model. We prove that any recursively enumerable language can be generated by a NEP where the derivation rules can be applied at arbitrarily chosen positions, the control of the communication is done by finite automata with at most three states, and either the rule sets are singletons or the underlying graph is a complete graph. If one uses networks with arbitrary underlying graphs and allows the additional application of insertions and deletions only to the right-most or the to left-most position of the derived words for some nodes, then we only need automata with only one state to control the communication in the network. Clearly, this result is optimal; moreover, finite automata with two states are necessary and sufficient in order to generate all the recursively enumerable languages when the derivation rules can be applied only at arbitrarily chosen positions.

Available Versions of this Item

• Networks of evolutionary processors: computationally complete normal forms (deposited 15 Mar 2013 14:42)
  • Networks of evolutionary processors: computationally complete normal forms (deposited 16 Apr 2013 14:31) [Currently Displayed]

Actions (login required)

View Item