Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Transducers based on Networks of Evolutionary Processors
Year:2014
Research Areas
  • Information technology and adata processing
Information
Abstract
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.
International
Si
JCR
No
Title
Journal of Automata, Languages and Combinatorics
ISBN
1430189X
Impact factor JCR
Impact info
Journal indexed in MathSciNet, Zentrallblatt Math, DBLP
Volume
19
Journal number
1-4
From page
93
To page
105
Month
SIN MES
Ranking
Participants
  • Autor: Sandra Maria Gomez Canaval (UPM)
  • Autor: Victor Mitrana (UPM)
  • Autor: Santiago Alonso Villaverde (UPM)
Research Group, Departaments and Institutes related
  • Creador: Departamento: Sistemas Informáticos
S2i 2020 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)