On Networks of Evolutionary Processors with Filters Accepted by Two-State-Automata

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

Abstrakty

EN

In this paper, we study networks of evolutionary processors where the filters are chosen as special regular sets. We consider networks where all the filters belong to a set of languages that are accepted by deterministic finite automata with a fixed number of states. We show that if the number of states is bounded by two, then every recursively enumerable language can be generated by such a network. If the number of states is bounded by one, then not all regular languages but non-context-free languages can be generated.

Słowa kluczowe

EN

evolutionary processors; language generating networks; state complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 112, nr 2/3
• Strony: 157--170
• Opis fizyczny: Bibliogr. 7 poz., wykr.

Twórcy

autor

Dassow J.

autor

Truthe B.

• Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, PSF 4120, 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, Fundam. Inform., 91, 2009, 1-15.
• [2] Castellanos, J., Mart´ın-Vide, C., Mitrana, V., Sempere, J. M.: Solving NP-Complete ProblemsWith Networks of Evolutionary Processors, IWANN '01: Proceedings of the 6th International Work-Conference on Artificial and Natural Neural Networks, LNCS 2084, Springer-Verlag Berlin, 2001, 621-628.
• [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-Varju, E., Salomaa, A.: Networks of Parallel Language Processors, New Trends in Formal Languages - Control, Cooperation, and Combinatorics (to J. Dassow on the occasion of his 50th birthday). LNCS 1218, Springer-Verlag Berlin, 1997, 299-318.
• [5] Dassow, J., Truthe, B.: On Networks of Evolutionary Processors with State Limited Filters, Second Workshop on Non-Classical Models of Automata and Applications (NCMA), Jena, Germany, August 23-24, 2010, Proceedings (H. Bordihn, R. Freund, T. Hinze, M. Holzer, M. Kutrib, F. Otto, Eds.), 263, Ősterreichische Computer Gesellschaft, Austria, 2010, 57-70.
• [6] Rozenberg, G., Salomaa, A.: Handbook of Formal Languages, Springer-Verlag, Berlin, 1997.
• [7] Starke, P. H.: Analyse von Petri-Netz-Modellen, B. G. Teubner-Verlag, Stuttgart, 1990.