Target Based Accepting Networks of Evolutionary Processors

• Autorzy: Truthe B.
• Języki publikacji: EN

Abstrakty

EN

In this paper, a new definition of accepting networks – called target based accepting networks – is given. In a target based accepting network of evolutionary processors, each node is equipped with a target condition. As soon as a node contains a word which satisfies the target condition of that node, the input word is accepted by the network. In this way, no further output nodes are necessary. Regarding the communication in a network, we consider two cases of control: 1. input and output filters are regular languages, then the target conditions are to belong to certain regular languages, 2. input and output filters are implemented as random context conditions, then the target condi- tions are given by sets of permitting and forbidding symbols. It is shown in both cases that conventional accepting networks and target based accepting networks have the same computational power. However, the number of processors needed for accepting a language can be reduced when using target based networks.

Słowa kluczowe

EN

networks of evolutionary network; regular filters; random context filter; target based acceptance

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 1/2
• Strony: 161--183
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Truthe B.

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

Bibliografia

• [1] Alhazov, A., Dassow, J., Martın-Vide, C., Rogozhin, Y., Truthe, B.: On networks of evolutionary processors with nodes of two types, Fundamenta Informaticae, 91, 2009, 1-15.
• [2] Alhazov, A., Martın-Vide, C., Rogozhin, Y.: On the number of nodes in universal networks of evolutionary processors, Acta Informatica, 43, 2006, 331-339.
• [3] Castellanos, J., Leupold, P., Mitrana, V.: On the size complexity of hybrid networks of evolutionary proces- sors, Theoretical Computer Science, 330, 2005, 205-220.
• [4] Castellanos, J., Mart´ın-Vide, C., Mitrana, V., Sempere, J.: Solving NP-complete problems with networks of evolutionary processors, Proc. IWANN, 2084, Springer-Verlag, Berlin, 2001, 621-628.
• [5] Castellanos, J., Martın-Vide, C., Mitrana, V., Sempere, J.: Networks of evolutionary processors, Acta Infor- matica, 38, 2003, 517-529.
• [6] Csuhaj-Varju, E., Salomaa, A.: Networks of parallel language processors, in: New Trends in Formal Language Theory, vol. 1218 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1997, 299-318.
• [7] Dassow, J., Mitrana, V.: Accepting networks of non-inserting evolutionary processors, Proceedings of NCGT 2008. Workshop on Natural Computing and Graph Transformations. September 8, 2008, Leicester, UK, University of Leicester, 2008, 29-41.
• [8] Loos, R., Manea, F., Mitrana, V.: Small universal accepting hybrid networks of evolutionary processors, Acta Informatica, 2010, To appear.
• [9] Mitrana, V., Truthe, B.: On accepting networks of evolutionary processors with at most two types of nodes, Language and Automata Theory and Applications, Third International Conference, LATA 2009, Tarragona, Spain, April 2009, Proceedings, 5457, Springer-Verlag, Berlin, 2009, 588-600.
• [10] Rozenberg, G., Salomaa, A.: Handbook of Formal Languages, Springer-Verlag, Berlin, 1997.
• [11] Truthe, B.: On small accepting networks of evolutionary processors with regular filters, Colloquium on the Occasion of the 50th Birthday of Victor Mitrana. Proceedings, Otto-von-Guericke-Universität Magdeburg, Germany, 2008, 37-52.