In this paper, we continue the research on accepting networks of evolutionary processors where the filters belong to several special families of regular languages. We consider families of codes or ideals and subregular families which are defined by restricting the resources needed for generating or accepting them (the number of states of the minimal deterministic finite automaton accepting a language of the family as well as the number of non-terminal symbols or the number of production rules of a right-linear grammar generating such a language). We insert the newly defined language families into the hierachy of language families obtained by using as filters languages of other subregular families (such as ordered, non-counting, power-separating, circular, suffix-closed regular, union-free, definite, combinational, finite, monoidal, nilpotent, or commutative languages).
Keywords: Network, evolutionary processor, computational power, regular filter, descriptional complexity, codes, ideals
@article{ITA_2021__55_1_A10_0,
author = {Dassow, J\"urgen and Truthe, Bianca},
editor = {Holzer, Markus and Sempere, Jos\'e M.},
title = {Accepting {Networks} of {Evolutionary} {Processors} {With} {Resources} {Restricted} and {Structure} {Limited} {Filters}},
journal = {RAIRO. Theoretical Informatics and Applications},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ita/2021004},
mrnumber = {4289540},
zbl = {1508.68188},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ita/2021004/}
}
TY - JOUR AU - Dassow, Jürgen AU - Truthe, Bianca ED - Holzer, Markus ED - Sempere, José M. TI - Accepting Networks of Evolutionary Processors With Resources Restricted and Structure Limited Filters JO - RAIRO. Theoretical Informatics and Applications PY - 2021 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ita/2021004/ DO - 10.1051/ita/2021004 LA - en ID - ITA_2021__55_1_A10_0 ER -
%0 Journal Article %A Dassow, Jürgen %A Truthe, Bianca %E Holzer, Markus %E Sempere, José M. %T Accepting Networks of Evolutionary Processors With Resources Restricted and Structure Limited Filters %J RAIRO. Theoretical Informatics and Applications %D 2021 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ita/2021004/ %R 10.1051/ita/2021004 %G en %F ITA_2021__55_1_A10_0
Dassow, Jürgen; Truthe, Bianca. Accepting Networks of Evolutionary Processors With Resources Restricted and Structure Limited Filters. RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 8. doi: 10.1051/ita/2021004
[1] , , and , Solving NP-complete problems with networks of evolutionary processors, in IWANN ’01: Proceedings of the 6th International Work-Conference on Artificial and Natural Neural Networks. Vol. 2084 of LNCS. Springer-Verlag, Berlin (2001) 621–628. | Zbl
[2] , , and , Networks of evolutionary processors. Acta Inf . 39 (2003) 517–529. | MR | Zbl | DOI
[3] and , Networks of parallel language processors, in New Trends in Formal Languages – Control, Cooperation, and Combinatorics. Vol. 1218 of LNCS. Springer-Verlag, Berlin (1997) 299–318. | MR
[4] , Grammars with control by ideals and codes. J. Autom. Lang. Combinat. 23 (2018) 143–164. | MR | Zbl
[5] , and , Networks of evolutionary processors: the power of subregular filters. Acta Inf . 50 (2013) 41–75. | MR | Zbl | DOI
[6] and , Accepting networks of non-inserting evolutionary processors, in Proceedings of NCGT 2008 – Workshop on Natural Computing and Graph Transformations, Leicester, United Kingdom, September 8, 2008, edited by and . University of Leicester (2008) 29–41.
[7] and , Networks of evolutionary processors with resources restricted filters. To appear in J. Autom. Lang. Combinat. (2019).
[8] and , Networks with evolutionary processors and ideals and codes as filters. To appear Int. J. Found. Comput. Sci. (2019). | MR | Zbl
[9] , The theory of regular events II. Kybernetika 5 (1969) 520–544. | MR | Zbl
[10] and , On relations between some subregular language families, in Seventh Workshop on Non-Classical Models of Automata and Applications (NCMA), Porto, Portugal, August 31 – September 1, 2015, Proceedings, edited by , , and . Vol. 318 of books@ocg.at. Österreichische Computer Gesellschaft (2015) 109–124.
[11] and , Codes, in vol. 1 of Handbook of Formal Languages, edited by and . Springer-Verlag, Berlin (1997) 511–607. | DOI
[12] and , Accepting networks of evolutionary processors with subregular filters. Theory Comput. Syst. 55 (2014) 84–109. | MR | Zbl | DOI
[13] , and , Accepting hybrid networks of evolutionary processors, in DNA Computing – 10th International Workshop on DNA Computing. Edited by , and . In Vol. 3384 of LNCS. Springer-Verlag, Berlin (2004) 235–246. | MR | Zbl
[14] and , Networks of evolutionary processors: Results and perspectives, in Molecular Computational Models: Unconventional Approaches, edited by . Idea Group Publishing (2005) 78–114. | DOI
[15] and , Handbook of Formal Languages. Springer-Verlag, Berlin (1997). | MR | Zbl
[16] , Free Monoids and Languages. Hon Min Book Company, Taichung, Taiwan (1991). | MR
[17] and , Ordered automata and associated languages. Tankang J. Math. 5 (1974) 9–20. | Zbl | MR
[18] and , Power-separating regular languages. Math. Syst. Theory 8 (1974) 90–95. | MR | Zbl | DOI
[19] , Hierarchy of subregular language families, Tech. Rep. 1801, Justus-Liebig-Universität Giessen, Institut für Informatik (2018).
[20] , Networks of evolutionary processors with resources restricted filters, in Tenth Workshop on Non-Classical Models of Automata and Applications (NCMA), Košice, Slovakia, August 21–22, 2018, Proceedings, edited by , , and . Vol. 332 of books@ocg.at. Österreichische Computer Gesellschaft (2018) 165–180.
[21] , Accepting networks of evolutionary processors with resources restricted filters, in Eleventh Workshop on Non-Classical Models of Automata and Applications (NCMA), Valencia, Spain, July 2–3, 2019, Proceedings, edited by , and . Vol. 336 of books@ocg.at. Österreichische Computer Gesellschaft (2019) 187–202.
[22] , Vergleich der Leistungsfähigkeit endlicher determinierter Automaten, diplomarbeit, Universität Rostock (1978).
Cité par Sources :
This paper is a revised and extended version of the paper presented at NCMA 2019 [21].
