Name
Abstract | ||
|---|---|---|
In this paper, we propose a hierarchy of families of languages generated by networks of evolutionary processors where the filters belong to 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 every regular language can be generated. If we use filters that are monoids, nilpotent languages, or commutative regular languages, we obtain one and 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 families of languages that one can use as filters in a network of evolutionary processors in order to obtain a complete computational model. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00236-012-0172-0 | Acta Informatica |
Keywords | Field | DocType |
Networks of evolutionary processors, Subregular languages, Generative power, 68Q05, 68Q42, 68Q45, 68Q85 | Generalized star height problem,Discrete mathematics,Combinatorics,Formal language,Comparison of multi-paradigm programming languages,Recursively enumerable language,Abstract family of languages,Cone (formal languages),Regular language,Third-generation programming language,Mathematics | Journal |
Volume | Issue | ISSN |
50 | 1 | 1432-0525 |
Citations | PageRank | References |
1 | 0.36 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jürgen Dassow | 1 | 530 | 118.27 |
| Florin Manea | 2 | 372 | 58.12 |
| Bianca Truthe | 3 | 159 | 28.57 |