Accepting Networks of Evolutionary Processors with Subregular Filters

We propose a new variant of Accepting Networks of Evolutionary Processors, in which the operations are applied at arbitrary positions to the processed words (rather than at the ends of words only) and where the filters are languages from several special classes of regular sets. More precisely, we show that the use of filters from the class of non-counting, ordered, power-separating, suffix-closed regular, union-free, definite and combinational languages is as powerful as the use of arbitrary regular languages and yields networks that can accept all the recursively enumerable languages. On the other hand, by using filters that are only finite languages, monoids, nilpotent languages, commutative regular languages, or circular regular languages, one cannot generate all recursively enumerable languages. These results seem interesting as they provide both upper and lower bounds on the classes of languages that one can use as filters in an accepting network of evolutionary processors in order to obtain a complete computational model.     

Networks of evolutionary processors

In this paper we consider networks of evolutionary processors as language generating and computational devices. When the filters are regular languages one gets the computational power of Turing machines with networks of size at most six, depending on the underlying graph. When the filters are defined by random context conditions, we obtain an incomparability result with the families of regular and context-free languages. Despite their simplicity, we show how the latter networks might be used for solving an NP-complete problem, namely the “3-colorability problem”, in linear time and linear resources (nodes, symbols, rules). Received: 26 September 2002 / 22 January 2003 RID="*" ID="*" Work supported by the Generalitat de Catalunya, Direcció General de Recerca (PIV2001-50).     

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.     

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.     

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.     

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.     

Regular patterns, regular languages and context-free languages

In this paper we consider two questions. First we consider whether every pattern language which is regular can be generated by a regular pattern. We show that this is indeed the case for extended (erasing) pattern languages if alphabet size is at least four. In all other cases, we show that there are patterns generating a regular language which cannot be generated by a regular pattern. Next we consider whether there are pattern languages which are context-free but not regular. We show that, for alphabet size 2 and 3, there are both erasing and non-erasing pattern languages which are context-free but not regular. On the other hand, for alphabet size at least 4, every erasing pattern language which is context-free is also regular. It is open at present whether there exist non-erasing pattern languages which are context-free but not regular for alphabet size at least 4.     

On the language equivalence of NE star-patterns

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting (non-empty) strings for variables. The pattern languages are one of language family which is orthogonal to the Chomsky-type languages hierarchy. They have many applications, such as the extended regular expressions, for instance, in languages Perl, awk, etc. They are well applicable in machine learning as well. There are erasing and non-erasing patterns are used. For non-erasing pattern languages the equivalence of languages is decidable but the inclusion problem for them is undecidable. In extended regular expressions one can use union, concatenation and Kleene star to make more complex patterns. It is also known, that the equivalence problem of extended regular expressions is undecidable. However, the problem, whether the equivalence is decidable for patterns using only concatenation and star still open. In this paper there are some interesting results about inclusion properties and equivalences of some kinds of erasing and non-erasing pattern languages. We show that the equivalence problem of non-erasing patterns in some cases can be reduced to the decidability problem of some very special inclusion properties. These results may be useful to decide whether the language equivalence of non-erasing star-patterns is decidable or not.     

The linear landscape of external contextual languages

The class of external contextual languages isstrictly included in the class of linear languages. A reason for the strict inclusion in linear languages is that external contextual grammars generate languages in the exhaustive way: each sentential form belongs to the language of a grammar. In this paper we study the effect of adding various squeezing mechanisms to the basic classes of exhaustive contextual grammars. We obtain in this way a characterization of linear languages and a whole landscape of sublinear families. By restricting the contexts to be one-sided (only left-sided or only right-sided) we obtain a characterization of regular languages — here the subregular landscape reduces to two families.     

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.     

Filtering random graphs to synthesize interconnection networks with multiple objectives

Synthesizing networks that satisfy multiple requirements, such as high reliability, low diameter, good embeddability, etc., is a difficult problem to which there has been no completely satisfactory solution. We present a simple, yet very effective, approach to this problem. The crux of our approach is a filtration process that takes as input a large set of randomly generated graphs and filters out those that do not meet the specified requirements. Our experimental results show that this approach is both practical and powerful. The use of random regular networks as the raw material for the filtration process was motivated by their surprisingly good performance with regard to almost all properties that characterize a good interconnection network. We provide results related to the generation of networks that have low diameter, high fault tolerance, and good embeddability. Through this, we show that the generated networks are serious competitors to several traditional well-known networks. We also explore how random networks can be used in a packaging hierarchy and comment on the scope of application of these networks.     

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.     

On the generative capacity of context-free matrix forms

This paper deals with the concepts of a matrix form and strict interpretation. By a matrix form we mean a context-free matrix grammar. Via an interpretation mechanism it generates a family of structurally related grammars and these generate a family of languages. We study here the properties of matrix forms as generators for the families of regular, linear and context-free languages. It is for instance shown that an arbitrary matrix form with only one nonterminal symbol does not generate the family of context-free languages if it contains a matrix with at least two productions.     

String and graph grammar characterizations of bounded regular languages

Two grammatical characterizations of the bounded regular languages are presented: one in terms of graph grammars, the other using string grammars. First it is shown that a class of state graphs recognizing the bounded regular languages can be generated by a particular second-order contextfree graph grammar. Next we call uniquely recursive a right-linear (string) grammar having at most one right-recursive production for each of its nonterminals. It is then established that the class of languages generated by uniquely recursive, sequential right-linear grammars is exactly the bounded regular languages. Some comments on the relationship between string and graph grammars are made.     

Formes de langages et de grammaires

Summary This paper is devoted to the study of context-free languages over infinite alphabets. This work can be viewed as a new attempt to study families of grammars, replacing the usual grammar forms and giving a new point of view on these questions. A language over an infinite alphabet or I-language appears as being a model for a family of usual languages; an interpretation is an homomorphism from the infinite alphabet to any finite alphabet. Using this notion of interpretation we can associate to each family of I-languages an image, called its shadow, which is a family of usual languages.The closure properties of families, generalizing to infinite alphabets the family of context-free languages, lead to define rational transductions between infinite alphabets or I-transductions, and then, families of I-languages closed under I-transductions, or I-cones. We study here relations between the closure properties of a family of I-languages and these of its shadow. As a result, we obtain that any union closed rational cone of context-free languages, principal or not, is the shadow of a principal I-cone.This work leads to new results about the classical theory of context-free languages. For instance, we prove that any principal rational cone of context-free languages can be generated by a context-free language, whose grammar has only 6 variables. This work also leads to more general considerations about the adequacy of some generating devices to the generated languages. It appears that the context-free grammars are fair, in a sense that we define, for generating context-free languages but that non-expansive context-free grammars are not for generating non-expansive context-free languages. This point of view raises a number of questions.     

Feedback automata and their languages

We introduce families of languages which are generated by deterministic and nondeterministic feedback-controlled models of automata. In case of the two deterministic models considered, the generated families are proper subclasses of the family of regular languages, where, in case of the nondeterministic model, the generated family equals the family of ?-free regular languages.