Complexity-preserving simulations among three variants of accepting networks of evolutionary processors (Q537856): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / 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. | |||
Property / 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jörg Desel / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68M07 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q85 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5898895 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
networks of evolutionary processors | |||
Property / zbMATH Keywords: networks of evolutionary processors / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
filtered connection | |||
Property / zbMATH Keywords: filtered connection / rank | |||
Normal rank |
Revision as of 09:28, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complexity-preserving simulations among three variants of accepting networks of evolutionary processors |
scientific article |
Statements
Complexity-preserving simulations among three variants of accepting networks of evolutionary processors (English)
0 references
23 May 2011
0 references
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.
0 references
networks of evolutionary processors
0 references
filtered connection
0 references