Computational Completeness of Networks of Evolutionary Processors with Elementary Polarizations and a Small Number of Processors - Descriptional Complexity of Formal Systems (DCFS 2017)
Conference Papers Year : 2017

Computational Completeness of Networks of Evolutionary Processors with Elementary Polarizations and a Small Number of Processors

Rudolf Freund
  • Function : Author
  • PersonId : 1022707
Vienna University of Technology = Technische Universität Wien
Vladimir Rogojin
  • Function : Author
  • PersonId : 1024594
Åbo Akademi University [Turku]
Sergey Verlan
Laboratoire d'Algorithmique Complexité et Logique
CV

Abstract

We improve previous results obtained for networks of evolutionary processors with elementary polarizations $-1,0,1$ by showing that only the very small number of seven processors is needed to obtain computational completeness. In the case of not requiring a special output node even only five processors are shown to be sufficient.

Domains

Computer Science [cs]
Fichier principal
Vignette du fichier
440206_1_En_11_Chapter.pdf (255.05 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Hal Ifip  : Connect in order to contact the contributor

https://inria.hal.science/hal-01657015

Submitted on : Wednesday, December 6, 2017-11:44:40 AM

Last modification on : Tuesday, March 5, 2024-9:18:04 AM

Download

Dates and versions

hal-01657015 , version 1 (06-12-2017)

Licence

Attribution

Identifiers

Cite

Rudolf Freund, Vladimir Rogojin, Sergey Verlan. Computational Completeness of Networks of Evolutionary Processors with Elementary Polarizations and a Small Number of Processors. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.140-151, ⟨10.1007/978-3-319-60252-3_11⟩. ⟨hal-01657015⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

LACL UPEC IFIP-LNCS IFIP IFIP-TC IFIP-TC1 IFIP-WG IFIP-DCFS IFIP-WG1-2 IFIP-LNCS-10316
188 View
105 Download

Altmetric

Share

More