On the Number of Nodes in Universal Networks of Evolutionary Processors (bibtex)
by Alhazov, Artiom, Martin-Vide, Carlos and Rogozhin, Yurii
Abstract:
We consider the networks of evolutionary processors (NEP) introduced by J.C.Castellanos, C.MartÃ­n-Vide, V.Mitrana and J.Sempere recently. We showed that every recursively enumerable (RE) language can be generated by an NEP with three nodes modulo a terminal alphabet and more, NEPs with four nodes can generate any RE language. Thus we improved existing universality result from five nodes down to four nodes. For mNEPs (a variant of NEPs where operations of different kinds are allowed in the same node) we got the optimal results: each RE language can be generated by an mNEP with one node modulo a terminal alphabet and mNEPs with two nodes can generate any RE language (it is not possible for mNEPs with one node). Some open problems are formulated.
Reference:
On the Number of Nodes in Universal Networks of Evolutionary Processors (Alhazov, Artiom, Martin-Vide, Carlos and Rogozhin, Yurii), In Acta Informatica, Springer-Verlag, volume 43, 2006.
Bibtex Entry:
@Article{j91,
author    = {Alhazov, Artiom AND Martin-Vide, Carlos AND Rogozhin, Yurii},
title     = {On the Number of Nodes in Universal Networks of Evolutionary Processors},
journal   = {Acta Informatica},
year      = {2006},
volume    = {43},
number    = {5},
pages     = {331-339},
abstract  = {We consider the networks of evolutionary processors (NEP) introduced by J.C.Castellanos, C.MartÃ­n-Vide, V.Mitrana and J.Sempere recently. We showed that every recursively enumerable (RE) language can be generated by an NEP with three nodes modulo a terminal alphabet and more, NEPs with four nodes can generate any RE language. Thus we improved existing universality result from five nodes down to four nodes. For mNEPs (a variant of NEPs where operations of different kinds are allowed in the same node) we got the optimal results: each RE language can be generated by an mNEP with one node modulo a terminal alphabet and mNEPs with two nodes can generate any RE language (it is not possible for mNEPs with one node). Some open problems are formulated.},
file      = {AMR2006a.pdf:pdfs/AMR2006a.pdf:PDF},
keywords  = {Distributed symbolic processing, Formal grammars, Cellular computing},
publisher = {Springer-Verlag},
}