Hybrid Networks of Evolutionary Processors

Carlos Martín-Vide¹, Victor Mitrana^2*, Mario J. Pérez-Jiménez^3**, and FernandoSancho-Caparrini³

¹Rovira i Virgili University,
Research Group in Mathematical Linguistics,
Pça. Imperial Tàrraco 1,
43005 Tarragona, Spain,
cmv@correu.urv.es

²University of Bucharest,
Faculty of Mathematics and Computer Science,
Str. Academiei 14,
70109 Bucharest, Romania,
mitrana@funinf.math.unibuc.ro

³University of Seville,
Department of Computer Science and Artificial Intelligence,
{Mario.Perez,Fernando.Sancho}@cs.us.es

Abstract. A hybrid network of evolutionary processors consists of several processors which are placed in nodes of a virtual graph and can perform one simple operation only on the words existing in that node in accordance with some strategies. Then the words which can pass the output filter of each node navigate simultaneously through the network and enter those nodes whose input filter was passed. We prove that these networks with filters defined by simple random-context conditions, used as language generating devices, are able to generate all linear languages in a very efficient way, as well as non-context-free languages. Then, when using them as computing devices, we present two linear solutions of the Common Algorithmic Problem.

^*Corresponding author. This work, done when this author was visiting the Department of Computer Science and Artificial Intelligence of the University of Seville, was supported by the Generalitat de Catalunya, Direcció General de Recerca (PIV2001-50)
^**Work supported by the project TIC2002-04220-C03-01 of the Ministerio de Ciencia y Tecnología of Spain, cofinanced by FEDER funds

LNCS 2723, p. 401 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003