Affiliations: Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, Universitätsplatz 2, D-39016 Magdeburg, Germany. [email protected] | Christian-Albrechts-Universität zu Kiel, Institut für Informatik, Christian-Albrechts-Platz 4, D-24098 Kiel, Germany. [email protected] | Justus-Liebig-Universität Gießen, Institut für Informatik, Arndtstr. 2, D-35392 Gießen, Germany. [email protected]
Note: [] Address for correspondence: Otto-von-Guericke-Universität Magdeburg, Fakultät für Inform., Universitätsplatz 2, D-39016 Magdeburg, Germany
Note: [] The work of Florin Manea was supported by the DFG grant 596676.
Note: [] The results were obtained while Bianca Truthe worked at the Otto-von-Guericke-Universität Magdeburg, Germany.
Abstract: In this paper, we approach the problem of accepting all recursively enumerable languages by accepting networks of evolutionary processors (ANEPs, for short) with a fixed architecture. More precisely, we show that every recursively enumerable language can be accepted by an ANEP with an underlying graph in the form of a star with 13 nodes or by an ANEP with an underlying grid with 13 × 4 = 52 nodes as well as by ANEPs having underlying graphs in the form of a chain, a ring, or a wheel with 29 nodes each. In all these cases, the size and form as well as the general working strategy of the constructed networks do not depend on the accepted language; only the rewriting rules and the filters associated to each node of the networks depend on this language. Noteworthy is also the fact that the filtering process is implemented using random context conditions only. Our results answer problems which were left open in a paper published by J. Dassow and F. Manea at the conference on Descriptional Complexity of Formal Systems (DCFS) 2010 and improve a result published by B. Truthe at the conference on Non-Classical Models of Automata and Applications (NCMA) 2013.
Keywords: Formal Languages, Networks of Evolutionary Processors, Computational Power, Random Context Conditions
