Transducers based on networks of evolutionary processors LOS FINANCIADORES NO ESTÁN BIEN

Gómez Canaval, Sandra; Mitrana, Victor y Alonso Villaverde, Santiago (2014). Transducers based on networks of evolutionary processors LOS FINANCIADORES NO ESTÁN BIEN. "Journal of Automata, Languages and Combinatorics", v. 19 (n. 1-4); pp. 93-105. ISSN 1430-189X.

Descripción

Título: Transducers based on networks of evolutionary processors LOS FINANCIADORES NO ESTÁN BIEN
Autor/es:
  • Gómez Canaval, Sandra
  • Mitrana, Victor
  • Alonso Villaverde, Santiago
Tipo de Documento: Artículo
Título de Revista/Publicación: Journal of Automata, Languages and Combinatorics
Fecha: 2014
Volumen: 19
Materias:
Palabras Clave Informales: Evolutionary rule; network of evolutionary processors; generalized sequential machine; NEP transducer
Escuela: E.T.S.I. de Sistemas Informáticos (UPM)
Departamento: Sistemas Informáticos
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (873kB) | Vista Previa

Resumen

We consider a new type of transducer that does not scan sequentially the input word. Instead, it consists of a directed graph whose nodes are processors which work in parallel and are specialized in just one type of a very simple evolutionary operation: inserting, deleting or substituting a symbol by another one. The computation on an input word starts with this word placed in a designated node, the input node, of the network an alternates evolutionary and communication steps. The computation halts as soon as another designated node, the output node, is nonempty. The translation of the input word is the set of words existing in the output node when the computation halts. We prove that these transducers can simulate the work of generalized sequential machines on every input. Furthermore, all words obtained by a given generalized sequential machine by the shortest computations on a given word can also be computed by the new transducers. Unlike the case of generalized sequential machines, every recursively enumerable language can be the transduction de?ned by the new transducer of a very simple regular language. The same idea may be used for proving that these transducers can simulate the shortest computations of an arbitrary Turing machine, used as a transducer, on every input word. Finally, we consider a restricted variant of NEP transducer, namely pure NEP transducers and prove that there are still regular languages whose pure NEP transductions are not semilinear.

Proyectos asociados

TipoCódigoAcrónimoResponsableTítulo
Sin especificarSin especificarSin especificarSin especificarTIN2011-28260-C03-03

Más información

ID de Registro: 39891
Identificador DC: http://oa.upm.es/39891/
Identificador OAI: oai:oa.upm.es:39891
URL Oficial: http://www.jalc.de/
Depositado por: Memoria Investigacion
Depositado el: 11 May 2017 18:26
Ultima Modificación: 11 May 2017 20:23
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM