Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Small universal accepting hybrid networks of evolutionary processors
Year:2010
Research Areas
  • Information technology and adata processing
Information
Abstract
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.
International
Si
JCR
Si
Title
ACTA INFORMATICA
ISBN
0001-5903
Impact factor JCR
0,923
Impact info
Volume
47
Journal number
2
From page
133
To page
146
Month
MARZO
Ranking
Participants
  • Autor: Victor Mitrana (UPM)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Grupo de Computación Natural
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)