Probabilities were recently introduced in Networks of Polarized Evolutionary Processors with the aim of decreasing the exponential expansion of the number of strings that appear in the computations used to solve NP-complete problems in a polynomial time, providing a new computational paradigm named Probabilistic Networks of Polarized Evolutionary Processors. Probabilities are associated with rules and words placed in the network nodes. Word probabilities are changed during the evolution and communication steps while the network is performing a computation. Probability associated with rules can be defined and fixed a priori (static mode) or may be computed dynamically (dynamic mode). There are also two possible ways of defining the halting and accepting conditions. The first possibility is to check whether there is some word in the halting node at the end of a communication step, and the second one is to say that a computation halts, with a determined cut-off point, if the sum of the of the probabilities of all words in the halting node is greater than or equal to a value in the set of (0,1]. The aim of this paper is to develop a generic software simulator of Probabilistic Networks of Polarized Evolutionary Processors (PNPEP) in order to study the probabilities of the strings arriving to the Halting node of the network.

A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages.

In this paper, we propose a solution to an NP-complete problem, namely the “3-colorability problem”, based on networks of polarized evolutionary processors. Our solution is uniform (it works for all instances of the same size) and time efficient (it works in linear time).