On the Power of Accepting Networks of Evolutionary Processors with Special Topologies and Random Context Filters

• Autorzy: Dassow J. , Manea F. , Truthe B.

Identyfikatory

DOI

10.3233/FI-2015-1142

• Języki publikacji: EN

Abstrakty

EN

In this paper, we approach the problemof 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.

Słowa kluczowe

EN

formal languages; networks of evolutionary processors; computational power; random context conditions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 1/2
• Strony: 1--35
• Opis fizyczny: Bibliogr. 18 poz., rys., tab.

Twórcy

autor

Dassow J.

• Otto-von-Guericke-Universität Magdeburg Fakultät für Informatik Universitätsplatz 2, D-39016 Magdeburg, Germany

autor

Manea F.

• Christian-Albrechts-Universität zu Kiel Institut für Informatik Christian-Albrechts-Platz 4, D-24098 Kiel, Germany

autor

Truthe B.

• Justus-Liebig-Universität Gießen Institut für Informatik Arndtstr. 2, D-35392 Gießen, Germany

Bibliografia

• [1] Alhazov, A., Csuhaj-Varjú, E., Martín-Vide, C., Rogozhin, Yu.: On the size of computationally complete hybrid networks of evolutionary processors, Theoretical Computer Science, 410(35), 2009, 3188–3197.
• [2] Castellanos, J.,Martın-Vide, C.,Mitrana, V., Sempere, J.M.: SolvingNP-Complete ProblemsWith Networks of Evolutionary Processors, IWANN ’01: Proceedings of the 6th Intern. Work-Conference on Artificial and Natural Neural Networks, 2084, Springer, 2001.
• [3] Castellanos, J., Martín-Vide, C., Mitrana, V., Sempere, J. M.: Networks of evolutionary processors, Acta Informatica, 39(6–7), 2003, 517–529.
• [4] Csuhaj-Varjú, E., Salomaa, A.: Networks of Parallel Language Processors, New Trends in Formal Languages – Control, Cooperation, and Combinatorics, 1218, Springer, 1997.
• [5] Dassow, J., Manea, F.: Accepting Hybrid Networks of Evolutionary Processors with Special Topologies and Small Communication, 12th Intern. Workshop on Descriptional Complexity of Formal Systems, EPTCS 31, 2010.
• [6] Dassow, J., Mitrana, V., Truthe, B.: The Role of Evolutionary Operations in Accepting Networks of Evolutionary Processors, Information and Computation, 209(3), 2011, 368–382.
• [7] Hartmanis, J., Stearns, R. E.: On the Computational Complexity of Algorithms, Transactions of the American Mathematical Society, 117, 1965, 285–306.
• [8] Kuroda, S.-Y.: Classes of Languages and Linear-Bounded Automata, Information and Control, 7(2), 1964, 207–223.
• [9] Loos, R.,Manea, F., Mitrana, V.: Small universal accepting hybrid networks of evolutionary processors, Acta Informatica, 47(2), 2010, 133–146.
• [10] Manea, F., Martín-Vide, C., Mitrana, V.: Accepting Networks of Evolutionary Word and Picture Processors: A Survey, in: Scientific Applications of Language Methods (C. Martín-Vide, Ed.), vol. 2 of Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory, World Scientific, 2010, 525–560.
• [11] Manea, F., Truthe, B.: Accepting Networks of Evolutionary Processors with Subregular Filters, 13th Intern. Conference on Automata and Formal Languages, College of Nyíregyháza, 2011.
• [12] Margenstern,M.,Mitrana, V., Pérez-Jiménez,M. J.: Accepting Hybrid Networks of Evolutionary Processors, 10th Intern. Workshop on DNA Computing, 3384, Springer, 2004.
• [13] Minsky, M.: Size and structure of universal Turing machines using tag systems, Recursive Function Theory: Proceedings, Symposium in Pure Mathematics, 5, 1962.
• [14] Post, E. L.: Formal Reductions of the General Combinatorial Decision Problem, American Journal of Mathematics, 65(2), 1943, 197–215.
• [15] Rogozhin, Y.: Small Universal Turing Machines, Theoretical Computer Science, 168(2), 1996, 215–240.
• [16] Rozenberg, G., Salomaa, A.: Handbook of Formal Languages, Springer-Verlag, Berlin, 1997.
• [17] Truthe, B.: Chains of Evolutionary Processors with Random Context Filters, Fifth Workshop on Non-Classical Models of Automata and Applications (NCMA), [e-mail], 2013.
• [18] Woods, D., Neary, T.: On the time complexity of 2-tag systems and small universal Turing machines, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’06, IEEE Computer Society,Washington, DC, USA, 2006, ISBN 0-7695-2720-5