Paper Info
Title
Networks of evolutionary processors with subregular filters
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.
Year
DOI
Venue
2011
10.1007/978-3-642-21254-3_20
LATA
Keywords
Field
DocType
combinational language,commutative regular language,complete computational model,subregular filter,finite language,regular set,nilpotent language,lower bound,arbitrary regular language,evolutionary processor,regular language
Generalized star height problem,Discrete mathematics,Combinatorics,Formal language,Computer science,Abstract family of languages,Cone (formal languages),Regular language,Third-generation programming language,Probabilistic automaton,Language family
Conference
Volume
ISSN
Citations 
6638
0302-9743
8
PageRank 
References 
Authors
0.59
17
3
Name
Order
Citations
PageRank
Jürgen Dassow1530118.27
Florin Manea237258.12
Bianca Truthe315928.57