Special Session NEPS 2009 Abstracts


Full Papers
Paper Nr: 1
Title:

ACCEPTING NETWORKS OF EVOLUTIONARY PROCESSORS: COMPLEXITY ASPECTS - Recent Results and New Challenges

Authors:

Florin Manea and Victor Mitrana

Abstract: In this paper we survey some results reported so far, for the new computational model of Accepting Networks of Evolutionary Processors (ANEPs), in the area of computational and descriptional complexity. First we give the definitions of the computational model, and its variants, then we define several ANEP complexity classes, and, further, we show how some classical complexity classes, defined for Turing Machines, can be characterized in this framework. After this, we briefly show how ANEPs can be used to solve efficiently NP-complete problems. Finally, we discuss a list of open problems and further directions of research which appear interesting to us.

Paper Nr: 2
Title:

ON THE SOLUTIONS OF NP-COMPLETE PROBLEMS BY MEANS OF JNEP RUN ON COMPUTERS

Authors:

Alfonso Ortega de la Puente, Carlos Castañeda Marroquín, Emilio del Rosal García, José Miguel Rojas Siles and Rafael Núñez Hervás

Abstract: We have used jNEP (a JAVA simulator of a natural computing device named Networks of Evolutionary Processors) to solve some cases of well-known NP-complete problems. We have followed the most relevant papers in the literature. In this paper, we describe the difficulties found in this process and some conclusions about the design, the simulation and some useful tools for NEPs.

Paper Nr: 3
Title:

OBLIGATORY HYBRID NETWORKS OF EVOLUTIONARY PROCESSORS

Authors:

Artiom Alhazov, Gemma Bel-Enguix and Yurii Rogozhin

Abstract: In this paper obligatory hybrid networks of evolutionary processors (a variant of hybrid networks of evolutionary processors model) are proposed. In the obligatory hybrid network of evolutionary processors a node discards the strings to which no operations are applicable. We show that such networks have the same computability power as Turing machines only using one operation per node (deletion on the left end and insertion on the right end of the string) no rewriting and no filters.

Paper Nr: 4
Title:

NETWORKS OF EVOLUTIONARY PROCESSORS AS NATURAL LANGUAGE PARSERS

Authors:

Alexander Perekrestenko, Gemma Bel-Enguix, M. Dolores Jiménez-López and Robert Mercaş

Abstract: Networks of Evolutionary Processors (NEPs) introduced in Castellanos et al. (2001) are a new computing mechanism directly inspired from the behaviour of cell populations. In the paper, we explore the possibility of using Networks of Evolutionary Processors (NEPs) for modelling natural language an entity generated in parallel by a modular architecture and specially syntax a modular device of specialized processors inside the modular construct of language. An implementation of NEPs for parsing of simple structures is suggested. Moreover, we introduce the concepts of parallel processing and linearity in the formalization of NEPs as accepting devices, and suggest a new line of research by applying these networks to natural language.

Paper Nr: 5
Title:

NETWORKS OF EVOLUTIONARY PROCESSORS - A Historical Account

Authors:

Carlos Martín-Vide, Gemma Bel-Enguix and M. Dolores Jiménez-López

Abstract: This paper provides a historical account of Networks of Evolutionary Processors (NEPs), a bioinspired model of computation based in the behaviour of colonies of cells. NEPs, introduced in (Castellanos et al., 2001), consist of several processors performing molecular operations, which are placed in an underlying graph. In the last years, NEPs have demonstrated their generating and accepting power, as well as a good capacity for solving hard computational problems. Whereas complexity results support the accuracy of the framework, different variants have been introduced in order to achieve several computational properties. In the future, NEPs can also be used as a model for research in other fields.

Paper Nr: 6
Title:

PARSING TREE ADJOINING GRAMMARS USING EVOLUTIONARY ALGORITHMS

Authors:

Adrian Horia Dediu and Cătălin Ionuţ Tîrnăucă

Abstract: We use evolutionary algorithms to speed up a rather complex process, the tree adjoining grammars parsing. This improvement is due due to a linear matching function which compares the fitness of different individuals. Internally, derived trees are processed as tree-to-string representations. Moreover, we present some practical results and a post running analysis that may encourage the use of evolutionary techniques in mildly context sensitive language parsing, for example.