Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 1
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Complexity-preserving simulations among three variants of accepting networks of evolutionary processors

  • Bottoni ., Paolo
  • Labella ., Anna
  • Manea ., Florin
  • Mitrana, Víctor
  • Petre ., Ion
  • Sempere Luna, José María|||0000-0003-2393-9224
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. © 2011 Springer Science+Business Media B.V., This work was supported by the Academy of Finland, projects 132727, 122426, and 108421. F. Manea acknowledges the support from the Alexander von Humboldt Foundation. J Sempere acknowledges the support from the Spanish Ministerio de Educacion y Ciencia project TIN2007-60769.