Abstract We propose an extension to the framework of reaction systems such that the environment not only plays the role of contributing entities to the successor state, but also influences the actual generation of products. In particular, we consider that an environment can assign valences to entities, be they used as reactants or inhibitors in a reaction, as well as select the entities which can appear in the successor state as product of a reaction. This provides a framework for immersing reaction system specifications into different contexts. We also derive a notion of polarised reaction systems , where entities can appear only as reactants or inhibitors in any given reaction. We compare the expressive power of the models, also showing some equivalences between them, and test them on three case studies derived from physiology, ecology, and chemistry.

We define a variant of accepting splicing system that can be used as a problem solver. A condition for halting the computation on a given input as well as a condition for making a decision as soon as the computation has stopped is considered. An algorithm based on this accepting splicing system that solves a well-known NP-complete problem, namely the 3-colorability problem is presented. We discuss an efficient solution in terms of running time and additional resources (axioms, supplementary symbols, number of splicing rules. More precisely, for a given graph with n vertices and m edges, our solution runs in O(nm) time, and needs O(mn2) other resources. Two variants of this algorithm of a reduced time complexity at an exponential increase of the other resources are finally discussed.

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.

The hairpin completion is a newly introduced operation on formal languages, inspired by biological phenomena and by DNA-computing. In this article, we analyse a new variant of the hairpin completion, called hairpin lengthening, which seems more appropriate for a possible bio-lab implementation. The variant considered here concerns the lengthening of the word that forms a hairpin structure, such that this structure is preserved, without necessarily completing the hairpin. First we present a series of language theoretic results regarding the one-step and iterated hairpin lengthening of languages from different classes of the Chomsky hierarchy. Following our biological motivation we also approach several algorithmic properties of this operation. More precisely, we propose an efficient algorithm for the recognition of the iterated hairpin lengthening of a language, and show how it can be particularized to recognize the one-step hairpin lengthening of a language; the cases when the starting language is finite, regular, linear context-free or context-free are discussed. It is worth noting that these results cannot be deduced canonically from the closure properties of the discussed classes of languages. We also propose an algorithm for computing efficiently the hairpin lengthening distance between a word and all its factors; this algorithm can be used to compute the distance between two words, or the common hairpin-lengthening ancestors of two words.

We extend the study of networks of evolutionary processors accepting words to a similar model, processing rectangular pictures. To this aim, we introduce accepting networks of evolutionary picture processors and investigate their computational power. We show that these networks can accept the complement of any local picture language as well as picture languages that are not recognizable. Some open problems regarding decidability issues and closure properties are finally discussed.

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).

In this paper we discuss the following interesting question about accepting hybrid networks of evolutionary processors (AHNEP), which are a recently introduced bio-inspired computing model. The question is: how many processors are required in such a network to recognise a given language L? Two answers are proposed for the most general case, when L is a recursively enumerable language, and both answers improve on the previously known bounds. In the first case the network has a number of processors that is linearly bounded by the cardinality of the tape alphabet of a Turing machine recognising the given language L. In the second case we show that an AHNEP with a fixed underlying structure can accept any recursively enumerable language. The second construction has another useful property from a practical point of view as it includes a universal AHNEP as a subnetwork, and hence only a limited number of its parameters depend on the given language.

Two strategies of parallel adjoining of contexts are considered for contextual grammars with choice. After a short comparison between them, there are provided Chomsky-Schutzenberger type characterizations of context-free and recursively enumerable la

We introduce two new grammatical interpretations which enlarge the grammatical collection of a given grammar. Briefly, the relations between these interpretations are presented, and also the effect on the generative capacity of a grammar system of the demand that all its components are similar to a given grammar. Especially, one obtains an important increase of the gene rative power if one requires that any component of the system is a b- or w-interpretation of a context free grammar.