Conţinutul numărului revistei |
Articolul precedent |
Articolul urmator |
34 0 |
SM ISO690:2012 ALHAZOV, Artiom, MARTIN-VIDE, Carlos, ROGOZHIN, Yurii. On the number of nodes in universal networks of evolutionary processors. In: Acta Informatica, 2006, vol. 43, pp. 331-339. ISSN 0001-5903. DOI: https://doi.org/10.1007/s00236-006-0024-x |
EXPORT metadate: Google Scholar Crossref CERIF DataCite Dublin Core |
Acta Informatica | ||||||
Volumul 43 / 2006 / ISSN 0001-5903 /ISSNe 1432-0525 | ||||||
|
||||||
DOI:https://doi.org/10.1007/s00236-006-0024-x | ||||||
Pag. 331-339 | ||||||
|
||||||
Descarcă PDF | ||||||
Rezumat | ||||||
We consider the networks of evolutionary processors (NEP) introduced by J. Castellanos, C. Martí n-Vide, V. Mitrana and J. Sempere recently. We show that every recursively enumerable (RE) language can be generated by an NEP with three nodes modulo a terminal alphabet and moreover, NEPs with four nodes can generate any RE language. Thus, we improve 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 obtain 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; this is not possible for mNEPs with one node. Some open problems are formulated. |
||||||
Cuvinte-cheie Evolutionary processors, Optimal results, Universal network |
||||||
|