## RC-International journal of Artificial intelligence

**Dead Line:**
**Acceptance notification:**
**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