Networks of evolutionary processors: computationally complete normal forms

Networks of evolutionary processors (NEPs, for short) form a bio-inspired language generating computational model that was shown to be equivalent to the model of phrase-structure grammars. In this paper, we analyse different restricted variants of NEPs that preserve the computational power of the general model. We prove that any recursively enumerable language can be generated by a NEP where the derivation rules can be applied at arbitrarily chosen positions, the control of the communication is done by finite automata with at most three states, and either the rule sets are singletons or the underlying graph is a complete graph. If one uses networks with arbitrary underlying graphs and allows the additional application of insertions and deletions only to the right-most or the to left-most position of the derived words for some nodes, then we only need automata with only one state to control the communication in the network. Clearly, this result is optimal; moreover, finite automata with two states are necessary and sufficient in order to generate all the recursively enumerable languages when the derivation rules can be applied only at arbitrarily chosen positions.     

Networks of evolutionary processors: the power of subregular filters

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.     

The role of evolutionary operations in accepting hybrid networks of evolutionary processors

In this paper, we investigate the role of evolutionary operations in accepting hybrid networks of evolutionary processors (AHNEP for short) in the following way. We consider AHNEPs with all the nodes specialized in only one evolutionary operation (substitution, insertion, or deletion) or in two operations out of these three. The considered variants differ in two respects: filters that are used to control the exchange of information (we use random context conditions and regular languages as filters) and the way of accepting the input word (at least one output node or all output nodes are non-empty at some moment in the computation). The computational power of all these variants is studied.     

Hybrid networks of evolutionary processors are computationally complete

A hybrid network of evolutionary processors (an HNEP) consists of several language processors which are located in the nodes of a virtual graph and able to perform only one type of point mutations (insertion, deletion, substitution) on the words found in that node, according to some predefined rules. Each node is associated with an input and an output filter, defined by some random-context conditions. After applying in parallel a point mutation to all the words existing in every node, the new words which are able to pass the output filter of the respective node navigate simultaneously through the network and enter those nodes whose input filter they are able to pass. We show that even the so-called elementary HNEPs are computationally complete. In this case every node is able to perform only one instance of the specified operation: either an insertion, or a deletion, or a substitution of a certain symbol. We also prove that in the case of non-elementary networks, any recursively enumerable language over a common alphabet can be obtained with an HNEP whose underlying structure is a fixed graph depending on the common alphabet only.Received: 19 July 2004, Published online: 19 January 2005Erzsébet Csuhaj-Varjú: Work supported in part by a grant from the NATO Scientific Committee in Spain and the Hungarian Scientific Research Fund OTKA Grant No. T 042529Victor Mitrana: Work supported by the Centre of Excellence in Information Technology, Computer Science and Control, ICA1-CT-2000-70025, HUN-TING project, WP5.     

On the size of computationally complete hybrid networks of evolutionary processors

A hybrid network of evolutionary processors (an HNEP) is a graph where each node is associated with an evolutionary processor (a special rewriting system), a set of words, an input filter and an output filter. Every evolutionary processor is given with a finite set of one type of point mutations (an insertion, a deletion or a substitution of a symbol) which can be applied to certain positions of a string over the domain of the set of these rewriting rules. The HNEP functions by rewriting the words that can be found at the nodes and then re-distributing the resulting strings according to a communication protocol based on a filtering mechanism. The filters are defined by certain variants of random-context conditions. HNEPs can be considered as both language generating devices (GHNEPs) and language accepting devices (AHNEPs). In this paper, by improving the previous results, we prove that any recursively enumerable language can be determined by a GHNEP and an AHNEP with 7 nodes. We also show that the families of GHNEPs and AHNEPs with 2 nodes are not computationally complete.     

On the number of nodes in universal networks of evolutionary processors

We consider the networks of evolutionary processors (NEP) introduced by J. Castellanos, C. Martí n-Vide, V. Mitrana and J. Sempere recently. We show that every recursively enumerable (RE) language can be generated by an NEP with three nodes modulo a terminal alphabet and moreover, NEPs with four nodes can generate any RE language. Thus, we improve existing universality result from five nodes down to four nodes. For mNEPs (a variant of NEPs where operations of different kinds are allowed in the same node) we obtain optimal results: each RE language can be generated by an mNEP with one node modulo a terminal alphabet, and mNEPs with two nodes can generate any RE language; this is not possible for mNEPs with one node. Some open problems are formulated.     

Complexity-preserving simulations among three variants of accepting networks of evolutionary processors

In this paper we consider three variants of accepting networks of evolutionary processors. It is known that two of them are equivalent to Turing machines. We propose here a direct simulation of one device by the other. Each computational step in one model is simulated in a constant number of computational steps in the other one while a translation via Turing machines squares the time complexity. We also discuss the possibility of constructing simulations that preserve not only complexity, but also the shape of the simulated network.     

Computational completeness of complete,star-like,and linear hybrid networks of evolutionary processors with a small number of processors

A hybrid network of evolutionary processors (HNEP) is a graph where each node is associated with a special rewriting system called an evolutionary processor, an input filter, and an output filter. Each evolutionary processor is given a finite set of one type of point mutations (insertion, deletion or a substitution of a symbol) which can be applied to certain positions in a string. An HNEP rewrites the strings in the nodes and then re-distributes them according to a filter-based communication protocol; the filters are defined by certain variants of random-context conditions. HNEPs can be considered both as languages generating devices (GHNEPs) and language accepting devices (AHNEPs); most previous approaches treated the accepting and generating cases separately. For both cases, in this paper we show that five nodes are sufficient to accept (AHNEPs) or generate (GHNEPs) any recursively enumerable language by showing the more general result that any partial recursive relation can be computed by an HNEP with (at most) five nodes with the underlying graph structure for the communication between the evolutionary processors being the complete or the linear graph with five nodes, whereas with a star-like communication graph we need six nodes. If the final results are defined by only taking the terminal strings out of the designated output node, then for these extended HNEPs we can prove that only four nodes are needed in all cases—for computing any partial recursive relation as well as for generating and accepting any recursively enumerable language—and the underlying communication structure can be a complete or a linear graph, but now even a star-like graph, too.     

Breaking the data encryption standard using networks of evolutionary processors with parallel string rewriting rules

In this paper we introduce a biologically inspired distributed computing model called networks of evolutionary processors with parallel string rewriting rules (NEPPS), which is a variation of the hybrid networks of evolutionary processors introduced by Martin-Vide et al. Such a network contains simple processors that are located in the nodes of a virtual graph. Each processor has strings (each string having multiple copies) and string rewriting rules. The rules are applied parallely on the strings. After the strings have been rewritten, they are communicated among the processors through filters. We show that we can theoretically break the DES (data encryption standard), which is the most widely used cryptosystem, using NEPPS. We prove that, given an arbitrary <plain-text, cipher-text> pair, one can recover the DES key in a constant number of steps.     

Speculative multithreaded processors

Speculation will overcome the limitations in dividing a single program into multiple threads that can execute on the multiple logical processing elements needed to enhance performance through parallelization     

Dedicated word processors

The word processing market has been growing at 30% for the past three or four years and is expected to continue this growth. The market is segmented between thin window and display word processing systems, and electronic typewriters. A brief look at the history of word processing (WP) is provided and the paper examines some recent trends in this market. The ‘unbundling’ of WP systems, WP support, the role of the microcomputer with WP package and the control of the introduction of these systems are discussed.     

Digit pipelined processors

Digit serial data transmission can be used to an advantage in the design of special purpose processors where communication issues dominate and where digit pipelining can be used to maintain high data rates. VLSI signal processing applications are one such problem domain. We have developed a family of VLSI components that have digit serial transmission and that can be pipelined at the digit level. These components can be used to construct VLSI processors that are especially suited to signal processing applications. One such particularly attractive processor is a structure we call the arithmetic cube. The arithmetic cube can be programmed to solve linear transformations such as convolutions and DFTs, and has nearest neighbor interconnects, regular layout, simple control, and a limited number of interconnections. Regular layout and simple control derive naturally from the algorithms on which the processor is based. Long wires are eliminated by the nearest neighbor interconnect. High throughput can be achieved by pipelining the processor at the digit level. The arithmetic cube is programmable in the problem size n; once implemented for a certain size N, smaller problems can be solved on the same implementation without a loss in performance. In addition, the architecture extends to larger N in a regular and automatic fashion.This work has been supported in part by the Army Research Office under Contract DAAG29-83-K-0126.     

Programmable stream processors

The demand for flexibility in media processing motivates the use of programmable processors. Stream processing bridges the gap between inflexible special-purpose solutions and current programmable architectures that cannot meet the computational demands of media-processing applications. The central idea behind stream processing is to organize an application into streams and kernels to expose the inherent locality and concurrency in media-processing applications. The performance of the Imagine stream processor on these media application is given.     

The mapping of 2-D array processors to 1-D array processors

We consider the case of a 2-dimensional wavefront array processor where only one wavefront appears at any time. We show that in such a situation, this 2-dimensional wavefront processor can be mapped to a linear array processor if the wavefronts never backtrack. The mapping will not increase the number of registers in each processor element. Two examples, the spoken words recognition problem and the longest common subsequence problem, are given to demonstrate the feasibility of this method.     

A routing defense mechanism using evolutionary game theory for Delay Tolerant Networks

Delay Tolerant Networks (DTNs) often suffer from intermittent disruption due to factors such as mobility and energy. Though lots of routing algorithms in DTNs have been proposed in the last few years, the routing security problems have not attracted enough attention. DTNs are still facing the threats from different kinds of routing attacks. In this paper, a general purpose defense mechanism is proposed against various routing attacks on DTNs. The defense mechanism is based on the routing path information acquired from the forwarded messages and the acknowledgment (ACK), and it is suitable for different routing schemes. Evolutionary game theory is applied with the defense mechanism to analyze and facilitate the strategy changes of the nodes in the networks. Simulation results show that the proposed evolutionary game theory based defense scheme can achieve high average delivery ratio, low network overhead and low average transmission delay in various routing attack scenarios. By introducing the game theory, the networks can avoid being attacked and provide normal transmission service. The networks can reach evolutionary strategy stable (ESS) under special conditions after evolution. The initial parameters will affect the convergence speed and the final ESS, but the initial ratio of the nodes choosing different strategies can only affect the game process.     

UNIX with satellite processors

The steps necessary to extend the UNIX

1 UNIX is a trademark of Bell Laboratories.

time sharing system to a network which includes a central processor and a set of satellite processors is described. Software interfaces permit a program in the satellite processor to behave as if it were running in the central processor. Tasks are executed in parallel in several processors resulting in improved reliability and response time. The economics of such systems becomes more feasible with the reduction of the cost of CPUs and memories and the increasing demand for dedicated local computers.