• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Complexity-Preserving Simulations Among Three Variants of Accepting Networks of Evolutionary Processors

Paolo Bottoni, Anna Labella, Florin Manea, Victor Mitrana, Ion Petre, Jose M. Sempere, Complexity-Preserving Simulations Among Three Variants of Accepting Networks of Evolutionary Processors. Natural Computing 10(1), 429–445, 2011.

Abstract:

In this paper we consider three variants of accepting networks of evolutionary processors. It
is known that two of them are equivalent to Turing machines. We propose here a direct
simulation of one device by the other. Each computational step in one model is simulated in
a constant number of computational steps in the other one while a translation via Turing
machines squares the time complexity. We also discuss the possibility of constructing
simulations that preserve not only complexity, but also the shape of the simulated network.

BibTeX entry:

@ARTICLE{jBoLaMaMiPeSe11a,
  title = {Complexity-Preserving Simulations Among Three Variants of Accepting Networks of Evolutionary Processors},
  author = {Bottoni, Paolo and Labella, Anna and Manea, Florin and Mitrana, Victor and Petre, Ion and Sempere, Jose M.},
  journal = {Natural Computing},
  volume = {10},
  number = {1},
  pages = {429–445},
  year = {2011},
  keywords = {Evolutionary processor; Uniform evolutionary processor; Network of evolutionary processors; Filtered connection},
}

Belongs to TUCS Research Unit(s): Computational Biomodeling Laboratory (Combio Lab)

Publication Forum rating of this publication: level 1

Edit publication