Complexity-preserving simulations among three variants of accepting networks of evolutionary processors (Q537856): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Importer (talk | contribs)
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
    0 references
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    networks of evolutionary processors
    0 references
    filtered connection
    0 references

    Identifiers