Paper Info
Title
Accepting Networks of Non-inserting Evolutionary Processors
Abstract
In this paper we consider four variants of accepting networks of evolutionary processors with in-place computations, that is the length of every word in every node at any step in the computation is bounded by the length of the input word. These devices are called here accepting networks of non-inserting evolutionary processors (ANNIEP shortly). The variants differ in two respects: filters that are used to control the exchange of information, i.e., we use random context conditions and regular languages as filters, and the way of accepting the input word, i.e., at least one output node or all output nodes are nonempty at some moment in the computation. The computational power of these devices is investigated. In the case of filters defined by regular languages, both variants lead to the class of context-sensitive languages. If random context conditions are used for defining filters, all linear context-free languages and some non-semilinear (even over the one-letter alphabet) can be accepted with both variants. Moreover, some closure properties of the classes of languages ANNIEPs with random context filters are also given.
Year
DOI
Venue
2009
10.1007/978-3-642-04186-0_9
T. Comp. Sys. Biology
Keywords
Field
DocType
non-inserting evolutionary processors,in-place computation,languages annieps,output node,closure property,random context filter,variants lead,input word,accepting networks,random context condition,regular language,evolutionary processor,context free language
Closure (mathematics),Computer science,Theoretical computer science,Regular language,Bounded function,Computation,Alphabet
Journal
Volume
ISSN
Citations 
11
0302-9743
4
PageRank 
References 
Authors
0.46
11
2
Name
Order
Citations
PageRank
Jürgen Dassow1530118.27
Victor Mitrana2950119.63