Functions and sequences generated by reaction systems (Q1935775)

A reaction system, introduced in [\textit{A. Ehrenfeucht} and \textit{G. Rozenberg}, Fundam. Inform. 75, No. 1--4, 263--280 (2007; Zbl 1108.68056)], defines a function from \(2^S\) (the set of subsets of a finite set \(S\)) into \(2^S\) itself: it consists of triples of the form \((R, I, P)\) (with \(R\), \(I\), \(P\) being subsets of \(S\)). The triples are called reactions, they are applied to a set as follows: \(R\) is the set of reactants, each of which has to be present for the reaction to take place, \(I\) is its set of inhibitors, none of which is allowed to be present, and \(P\) is its set of products, each of which will be present after a successful reaction. The reaction system maps a subset \(T\) of \(S\) to \(T'\) by applying all the reactions that are enabled in \(T\), and collecting all the products in \(T'\). Such a function is total if it is defined for all proper nonempty subsets of \(S\), and a reaction system is functionally complete if all total functions are defined by systems that are so-called `core equivalent' to it. The paper gives a characterization of reaction systems defining total functions in the case of having singleton sets as reactants and inhibitors, and gives a characterization of functionally complete systems as well. Hierarchies of functions are also presented based on the amount of resources, that is, the maximal cardinality of the sets of reactants and inhibitors. In the last part of the paper, sequences and cycles of sets generated by reaction systems are also considered.