|
|||||
|
|
Networks of evolutionary processors |
|
| Authors: | Juan Castellanos Carlos Martín-Vide Victor Mitrana José M Sempere |
| Affiliation: | Department of Artificial Intelligence, Polytechnical University of Madrid, 28660 Boadilla del Monte, Madrid, Spain (e-mail: jcastellanos@fi.upm.es), ES Research Group in Mathematical Linguistics, Rovira i Virgili University, P?a. Imperial Tàrraco 1, 43005 Tarragona, Spain (e-mail: cmv@correu.urv.es), ES Faculty of Mathematics, University of Bucharest, Str. Academiei 14, 70109 Bucharest, Romania (e-mail: mitrana@funinf.math.unibuc.ro), RO Department of Information Systems and Computation, Polytechnical University of Valencia, Valencia 46071, Spain (e-mail: jsempere@dsic.upv.es), ES |
| Abstract: | In this paper we consider networks of evolutionary processors as language generating and computational devices. When the filters are regular languages one gets the computational power of Turing machines with networks of size at most six, depending on the underlying graph. When the filters are defined by random context conditions, we obtain an incomparability result with the families of regular and context-free languages. Despite their simplicity, we show how the latter networks might be used for solving an NP-complete problem, namely the “3-colorability problem”, in linear time and linear resources (nodes, symbols, rules). Received: 26 September 2002 / 22 January 2003 RID="*" ID="*" Work supported by the Generalitat de Catalunya, Direcció General de Recerca (PIV2001-50). |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |