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.

Complexity-preserving simulations among three variants of accepting networks of evolutionary processors / Bottoni, Paolo Gaspare; Labella, Anna; Florin, Manea; Victor, Mitrana; Ion, Petre; Jose M., Sempere. - In: NATURAL COMPUTING. - ISSN 1567-7818. - STAMPA. - 10:1(2011), pp. 429-445. [10.1007/s11047-010-9238-5]

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

BOTTONI, Paolo Gaspare;LABELLA, Anna;
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.
2011
evolutionary processor; filtered connection; network of evolutionary processors; uniform evolutionary processor
01 Pubblicazione su rivista::01a Articolo in rivista
Complexity-preserving simulations among three variants of accepting networks of evolutionary processors / Bottoni, Paolo Gaspare; Labella, Anna; Florin, Manea; Victor, Mitrana; Ion, Petre; Jose M., Sempere. - In: NATURAL COMPUTING. - ISSN 1567-7818. - STAMPA. - 10:1(2011), pp. 429-445. [10.1007/s11047-010-9238-5]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/39925
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 9
social impact