Research Cloud ® TM

RC-International journal of Artificial intelligence

Full Paper Submission:
Publishing date:

A formal model of reaction systems was a few years ago introduced in [4]. The original purpose was to model interactions between biochemical reactions. The reference [4] contains some of the original motivation and initial setup. Each reaction is characterized by its set of reactants, each of which has to be present for the reaction to take place, by its set of inhibitors, none of which is allowed to be present, and by its set of products, each of which will be present after a successful reaction. Thus, a single reaction is based on facilitation and inhibition. Everything is defined within a fixed finite background set S. The sets of reactants, inhibitors and products, R, I and P, are nonempty subsets of S, the sets R and I being disjoint. A reaction system RS consists of finitely many such triples (R, I, P), called reactions. The application of RS to a subset Y of S (to be explained in detail below) produces another subset Y ′ of S and, thus, we have a function from subsets of S to subsets of S. Iterating the function we get a sequence of subsets of S, referred to as states of the sequence. Altogether this gives a new kind of mechanism for generating functions and sequences over a finite set.The model of reaction systems turned out to be suitable in different setups. Then also many variants of the systems and additions to them were introduced. The reference [1] constitutes a recent survey. However, in this paper we are concerned with the basic variant only. We now outline the contents of this paper. The exposition is largely selfcontained. The basic definitions are given in Section 2, together with some illustrative examples. The exposition is focused on the needs of the next sections. Section 3 discusses propositional formulas with monotonic truth-functions. Section 4 generalizes the discussion and proves the material needed in Section 5, where the main NP-completeness results are established. The paper is concluded with considerations concerning the connection between many-valued propositional logic and reaction systems

Read more | March 15, 2015