Manea, Florin (2012) Complexity results for deciding Networks of Evolutionary Processors. Theoretical Computer Science, 456 . pp. 65-79. DOI 10.1016/j.tcs.2012.06.029.

Preview

Text TCS_rev.pdf Download (387kB) | Preview

Abstract

The Accepting Networks of Evolutionary Processors (ANEPs for short) are bio-inspired computational models which were introduced and thoroughly studied in the last decade. In this paper we propose a method of using ANEPs as deciding devices. More precisely, we define a new halting condition for this model, which seems more coherent with the rest of the theory than the previous such definitions, and show that all the computability related results reported so far remain valid in the new framework. Further, we are able to show a direct and efficient simulation of an arbitrary ANEP by an ANEP having a complete underlying graph; as a consequence of this result, we conclude that the efficiency of deciding a language by ANEPs is not influenced by the network’s topology. Finally, focusing on the computational complexity of ANEP-based computations, we obtain a surprising characterisation of $P^{NP[log]}$ as the class of languages that can be decided in polynomial time by such networks.

Available Versions of this Item

• Complexity results for deciding Networks of Evolutionary Processors (deposited 15 Mar 2013 14:42)
  • Complexity results for deciding Networks of Evolutionary Processors (deposited 16 Apr 2013 14:32) [Currently Displayed]

Actions (login required)

View Item