Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
Small universal accepting hybrid networks of evolutionary processors
Año:2010
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
In this paper, we improve some results regarding the size complexity of accepting hybrid networks of evolutionary processors (AHNEPs).We show that there are universal AHNEPs of size 6, by devising a method for simulating 2-tag systems. This result improves the best upper bound for the size of universal AHNEPs which was 7.We also propose a computationally and descriptionally efficient simulation of nondeterministic Turing machines with AHNEPs. More precisely, we prove that AHNEPs with ten nodes can simulate any nondeterministic Turing machine of time complexity f (n) in time O( f (n)). This result significantly improves the best known upper bound for the number of nodes in a network simulating in linear time an arbitrary Turing machine, namely 24.
Internacional
Si
JCR del ISI
Si
Título de la revista
ACTA INFORMATICA
ISSN
0001-5903
Factor de impacto JCR
0,923
Información de impacto
Volumen
47
DOI
Número de revista
2
Desde la página
133
Hasta la página
146
Mes
MARZO
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Victor Mitrana (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Grupo de Computación Natural
S2i 2021 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)