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

DOI10.1007/S11047-010-9238-5MaRDI QIDQ537856zbMATH OpenOpenAlexFDO

Authors Paolo Bottoni, Anna Labella, Florin Manea, Victor Mitrana, Ion Petre, Jose M. Sempere

Publication date 23 May 2011

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11047-010-9238-5

zbMATH Keywords

filtered connectionnetworks of evolutionary processors

Mathematics Subject Classification ID

Mathematical problems of computer architecture (68M07) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Review text

This paper considers three variants of accepting networks of evolutionary processors. Two of them are known to be equivalent to Turing machines. A direct simulation of one device by the other is introduced, where each computational step in one model is simulated in a constant number of computational steps in the other model, whereas a translation via Turing machines squares the time complexity. Moreover, simulations that do not only preserve complexity but also the shape of the considered network are discussed.

Recommendations

• A survey on computationally complete accepting and generating networks of evolutionary processors
• Complexity results for deciding networks of evolutionary processors
• ON THE DESCRIPTIONAL COMPLEXITY OF ACCEPTING NETWORKS OF EVOLUTIONARY PROCESSORS WITH FILTERED CONNECTIONS
• On the size complexity of universal accepting hybrid networks of evolutionary processors
• On Accepting Networks of Evolutionary Processors with at Most Two Types of Nodes
• On the Power of Networks of Evolutionary Processors
• On the power of accepting networks of evolutionary processors with special topologies and random context filters
• Accepting Networks of Non-inserting Evolutionary Processors
• scientific article; zbMATH DE number 2001369

Cites work

• Accepting networks of evolutionary processors with filtered connections
• Computing with membranes
• DNA Computing
• Evolutionary systems: A language generating device inspired by evolving communities of cells
• Filter position in networks of evolutionary processors does not matter: a direct proof
• scientific article; zbMATH DE number 1728707 (Why is no real title available?)
• scientific article; zbMATH DE number 23841 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Networks of Evolutionary Picture Processors with Filtered Connections
• ON THE DESCRIPTIONAL COMPLEXITY OF ACCEPTING NETWORKS OF EVOLUTIONARY PROCESSORS WITH FILTERED CONNECTIONS
• On the Power of Networks of Evolutionary Processors
• On the size complexity of universal accepting hybrid networks of evolutionary processors
• On the size of computationally complete hybrid networks of evolutionary processors
• Smallest filters in complete obligatory hybrid networks of evolutionary processors

Cited in

(8)

• Filters defined by random contexts versus polarization in networks of evolutionary processors
• A survey on computationally complete accepting and generating networks of evolutionary processors
• Simulating polarization by random context filters in networks of evolutionary processors
• Polarization: a new communication protocol in networks of bio-inspired processors
• On the computational power of networks of polarized evolutionary processors
• Small networks of polarized splicing processors are universal
• Networks of evolutionary processors: wheel graph simulation
• Complexity results for deciding networks of evolutionary processors

This page was built for publication: Complexity-preserving simulations among three variants of accepting networks of evolutionary processors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q537856)