Networks of polarized evolutionary processors are computationally complete

Arroyo Montoro, Fernando and Gomez Canaval, Sandra and Mitrana, Victor and Popescu, Stefan (2014). Networks of polarized evolutionary processors are computationally complete. In: "8th International Conference, LATA 2014 Madrid, Spain, March 10-14, 2014 : Proceedings", 10-14 de marzo de 2014, Madrid, España. ISBN 978-3-319-04920-5. pp. 101-112. https://doi.org/10.1007/978-3-319-04921-2_8.

Description

Title: Networks of polarized evolutionary processors are computationally complete
Author/s:
  • Arroyo Montoro, Fernando
  • Gomez Canaval, Sandra
  • Mitrana, Victor
  • Popescu, Stefan
Item Type: Presentation at Congress or Conference (Article)
Event Title: 8th International Conference, LATA 2014 Madrid, Spain, March 10-14, 2014 : Proceedings
Event Dates: 10-14 de marzo de 2014
Event Location: Madrid, España
Title of Book: Language and automata theory and applications : 8th International Conference, LATA 2014 Madrid, Spain, March 10-14, 2014 : Proceedings
Date: 2014
ISBN: 978-3-319-04920-5
Volume: 8370
Subjects:
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (832kB) | Preview

Abstract

ABSTRACT In this paper, we consider the computational power of a new variant of networks of evolutionary processors which seems to be more suitable for a software and hardware implementation. Each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined, the data polarization is dynamically computed by means of a valuation mapping. Consequently, the protocol of communication is naturally defined by means of this polarization. We show that tag systems can be simulated by these networks with a constant number of nodes, while Turing machines can be simulated, in a time-efficient way, by these networks with a number of nodes depending linearly on the tape alphabet of the Turing machine.

More information

Item ID: 41613
DC Identifier: http://oa.upm.es/41613/
OAI Identifier: oai:oa.upm.es:41613
DOI: 10.1007/978-3-319-04921-2_8
Official URL: https://link.springer.com/chapter/10.1007/978-3-319-04921-2_8
Deposited by: Memoria Investigacion
Deposited on: 09 Jun 2017 18:00
Last Modified: 09 Jun 2017 18:00
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM