Abstract
In this paper we propose a hierarchy of classes of languages, generated by networks of evolutionary processors with the filters in several special classes of regular sets. More precisely, we show that the use of filters from the class of ordered, non-counting, power-separating, circular, suffix-closed regular, union-free, definite and combinational languages is as powerful as the use of arbitrary regular languages and yields networks that can generate all the recursively enumerable languages. On the other hand, the use of filters that are only finite languages allows only the generation of regular languages, but not all regular languages can be generated. If we use filters that are monoids, nilpotent languages or commutative regular languages, we obtain the same family of languages which contains non-context-free languages but not all regular languages. These results seem to be of interest because they provide both upper and lower bounds on the classes of languages that one can use as filters in a network of evolutionary processor in order to obtain a complete computational model.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
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, 1–15 (2009)
Bordihn, H., Holzer, M., Kutrib, M.: Determinization of finite automata accepting subregular languages. Theoretical Computer Science 410, 3209–3222 (2009)
Brzozowski, J., Jirásková, G., Li, B.: Quotient complexity of ideal languages. In: López-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 208–221. Springer, Heidelberg (2010)
Castellanos, J., Martín-Vide, C., Mitrana, V., Sempere, J.M.: Solving NP-complete problems with networks of evolutionary processors. In: Mira, J., Prieto, A.G. (eds.) IWANN 2001. LNCS, vol. 2084, pp. 621–628. Springer, Heidelberg (2001)
Castellanos, J., Martín-Vide, C., Mitrana, V., Sempere, J.M.: Networks of evolutionary processors. Acta Informatica 39(6-7), 517–529 (2003)
Csuhaj-Varjú, E., Salomaa, A.: Networks of parallel language processors. In: Păun, G., Salomaa, A. (eds.) New Trends in Formal Languages. LNCS, vol. 1218, pp. 299–318. Springer, Heidelberg (1997)
Dassow, J.: Subregularly controlled derivations: the context-free case. Rostocker Mathematisches Kolloquium 34, 61–70 (1988)
Dassow, J.: Grammars with commutative, circular, and locally testable conditions. In: Automata, Formal Languages, and Related Topics – Dedicated to Ferenc Gécseg on the Occasion of his 70th Birthday, pp. 27–37. University of Szeged (2009)
Dassow, J., Hornig, H.: Conditional grammars with subregular conditions. In: Proc. Internat. Conf. Words, Languages and Combinatorics II, pp. 71–86. World Scientific, Singapore (1994)
Dassow, J., Manea, F., Truthe, B.: Networks of evolutionary processors with subregular filters. Technical report, Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik (2011), http://theo.cs.uni-magdeburg.de/pubs/preprints/pp-afl-2011-01.pdf
Dassow, J., Stiebe, R., Truthe, B.: Generative capacity of subregularly tree controlled grammars. International Journal of Foundations of Computer Science 21, 723–740 (2010)
Dassow, J., Truthe, B.: On networks of evolutionary processors with filters accepted by two-state-automata. Fundamenta Informaticae (to appear)
Han, Y.S., Salomaa, K.: State complexity of basic operations on suffix-free regular languages. Theoretical Computer Science 410(27–29), 2537–2548 (2009)
Han, Y.S., Salomaa, K., Wood, D.: Nondeterministic state complexity of basic operations for prefix-suffix-free regular languages. Fundamenta Informaticae 90(1-2), 93–106 (2009)
Havel, I.M.: The theory of regular events II. Kybernetika 5(6), 520–544 (1969)
Holzer, M., Jakobi, S., Kutrib, M.: The magic number problem for subregular language families. In: Proceedings of 12th Internat. Workshop Descriptional Complexity of Formal Systems, pp. 135–146. University of Saskatchewan, Saskatoon (2010)
Jirásková, G., Masopust, T.: Complexity in union-free languages. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol. 6224, pp. 255–266. Springer, Heidelberg (2010)
Martín-Vide, C., Mitrana, V.: Networks of evolutionary processors: Results and perspectives. In: Molecular Computational Models: Unconventional Approaches, pp. 78–114 (2005)
Rozenberg, G., Salomaa, A.: Handbook of Formal Languages. Springer, Berlin (1997)
Wiedemann, B.: Vergleich der Leistungsfähigkeit endlicher determinierter Automaten. Diplomarbeit, Universität Rostock (1978)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dassow, J., Manea, F., Truthe, B. (2011). Networks of Evolutionary Processors with Subregular Filters. In: Dediu, AH., Inenaga, S., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2011. Lecture Notes in Computer Science, vol 6638. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21254-3_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-21254-3_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21253-6
Online ISBN: 978-3-642-21254-3
eBook Packages: Computer ScienceComputer Science (R0)