On Networks of Evolutionary Processors with Nodes of Two Types

• Autorzy: Alhazov A. , Martin-Vide C. , Truthe B. , Dassow J. , Rogozhin Y.
• Języki publikacji: EN

Abstrakty

EN

We discuss the power of networks of evolutionary processors where only two types of nodes are allowed. We prove that (up to an intersection with a monoid) every recursively enumerable language can be generated by a network with one deletion and one insertion node. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficient. Networks with an arbitrary number of insertion and substitution nodes only generate context-sensitive languages, and (up to an intersection with a monoid) every context-sensitive language can be generated by a network with one substitution node and one insertion node. All results are optimal with respect to the number of nodes.

Słowa kluczowe

EN

network; evolutionary processors; insertion; deletion; substitution; recursively enumerable languages; context sensitive languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 1
• Strony: 1--15
• Opis fizyczny: bibliogr. 13 poz.

Twórcy

autor

Alhazov A.

autor

Martin-Vide C.

autor

Truthe B.

autor

Dassow J.

autor

Rogozhin Y.

• Abo Akademi University Dept. of Information Technologies Turku Center for Comp.Sc. FIN-20520 Turku, Finland,

Bibliografia

• [1] Alhazov, A., Martín-Vide, C., Rogozhin, Yu.: On the number of nodes in universal networks of evolutionary processors, Acta Inf. 43 (2006) 331-339.
• [2] Alhazov, A., Martín-Vide, C., Rogozhin, Yu.: Networks of Evolutionary Processors with Two Nodes Are Unpredictable, Technical Report 35/07, Rovira i Virgili University, Language and Automata Theory and Applications, Tarragona, 521-527 (2007) and TUCS Report 818, Turku (2007), www.tucs.fi.
• [3] Castellanos, J., Leupold, P., Mitrana, V.: On the size complexity of hybrid networks of evolutionary processors, Theor. Comput. Sci. 330 (2005) 205-220.
• [4] Castellanos, J., Martín-Vide, C., Mitrana, V., Sempere, J.: Solving NP-complete problems with networks of evolutionary processors, in: Proc. IWANN, Lecture Notes in Computer Science 2084, Springer-Verlag, Berlin, 2001, 621-628.
• [5] Castellanos, J., Martín-Vide, C., Mitrana, V., Sempere, J.: Networks of evolutionary processors, Acta Inf. 38 (2003) 517-529.
• [6] Csuhaj-Varjú, E.,Martín-Vide, C., Mitrana, V.: Hybrid networks of evolutionary processors are computationally complete, Acta Inf. 41 (2005) 257-272.
• [7] Csuhaj-Varjú, E., Salomaa, A.: Networks of parallel language processors, in: New Trends in formal Language Theory (Gh. Păun, A. Salomaa, Eds.), Lecture Notes in Computer Science 1218, Springer-Verlag, Berlin, 1997, 299-318.
• [8] Dassow, J.: On special networks of parallel language processors, Romanian Journal of Information Science and Technology 1 (1998) 331-341.
• [9] Dassow, J., Păun, Gh.: Regulated Rewriting in Formal Language Theory. Springer-Verlag, Berlin, 1989.
• [10] Fahlmann, S. E., Hinton, G. E., Seijnowski, T. J.: Massively parallel architectures for AI: NETL, THISTLE and Boltzmann machines, in: Proc. AAAI National Conf. on AI, William Kaufman, Los Altos, 1983, 109-113.
• [11] Hillis, W. D.: The Connection Machine. MIT Press, Cambridge, 1985.
• [12] Margenstern,M., Păun, Gh., Rogozhin, Yu., Verlan; S.: Context-free insertion-deletion systems, Theor. Comput. Sci. 330 (2005) 339-348.
• [13] Rozenberg, G., Salomaa, A.: Handbook of Formal Languages. Springer-Verlag, Berlin, 1997.