Second International Workshop on Reaction Systems

The workshop will take place from Wednesday, June 5, until Friday, June 7. The workshop program will cover the recent as well as the established scientific results. Also, presentations of work in progress are welcome.

Invited speakers

• Roberta Gori, Pisa, Italy – Causalities in reaction systems
• Giancarlo Mauri, Milano, Italy – Membrane systems and computational complexity

Workshop Program

Wednesday, June 5

Thursday, June 6

Friday, June 7

Abstracts of the talks

Causalities in reaction systems
Roberta Gori, Pisa, Italy

Causalities in reaction systems describe the ways in which entities influence each other. The main idea to study dynamic causalities is the concept of predictor, originally introduced by Brijder, Ehrenfeucht and Rozenberg, that can be summarized as follows. Assume that you are interested in a particular object s and in knowing if that object s will be present after a given number n of steps of execution of the reaction system. Since the only source of non-determinism are the contextual elements received at each step from the environment, knowing which objects will be received at each step can allow the production of s after n steps to be predicted. The concept of predictor is based on the idea that, in general, not all contextual elements are relevant for determining if s will be produced after n steps. Indeed, for given s and n, there might be a subset of objects (the predictor, indeed) that is essential to observe in contextual elements for predicting whether or not s will be produced after n steps. We pushed forward the previous idea by defining the notion of formula based predictor, i.e., a propositional logic formula fully characterizing all the sequences of objects produced by the environment that lead to the production of the desired object in the required number of steps. This new notion comes equipped with an effective operator able to compute it. Restricting our attention to Closed Reaction Systems, the notion of formula based predictor becomes the Ancestor formula able to characterize all the n-ancestors of a given object of interest. Indeed, ancestors in closed reaction system consist of all the initial configurations that lead to the production of an object in a given number of steps. These concepts are applied to reaction systems modelling gene regulatory networks.

Joint research with R. Barbuti, F. Levi and P. Milazzo.

Membrane systems and computational complexity
Giancarlo Mauri, Milano, Italy

Membrane systems (or P systems) were introduced by G. Paun as a class of distributed parallel computing devices inspired by the functioning of living cells. The basic model consists of several membranes, hierarchically embedded in a main membrane called skin membrane. The membranes delimit regions and can contain objects, which evolve according to given evolution rules associated with the regions, applied in a nondeterministic and maximally parallel manner. If we let the system evolve starting from a given initial configuration, we obtain a computation. The computation halts if no further rule can be applied, and the objects expelled through the skin membrane (or collected inside a specified output membrane) are the result of the computation. Many variants of P systems have been defined, adding further features or capabilities to the basic model, or controlling in different ways the application of the evolution rules. An obvious question that arises concerns the definition of classes of (decision) problems that can be solved by P systems within given bounds of time/space, adapting to the framework of P systems notions from classical structural complexity theory, and the possibility of attacking computationally hard problems (e.g., NP -complete problems) using a polynomial amount of resources. In this talk I will discuss the problems related to the definition of time/space complexity classes for membrane systems, in their different variants, and the resulting hierarchy will be compared with the usual hierarchy of complexity classes, mainly through simulations of Turing Machines by (uniform families of) membrane systems.

Joint research with A. Leporati, L. Manzoni, A.E. Porreca and C. Zandron.

Elementary reaction systems
Luca Manzoni, Milano, Italy

Elementary reaction systems (RS) are a restriction of classical RS in which a function mapping entities to subset of entities uniquely determines the products of a reaction. We continue our investigation of the notion of simulability between classes of reaction systems, with an emphasis of the ability of elementary reaction systems to simulate more general systems with only a limited slowdown and increase in size. We show that elementary RS can weakly simulate all classical RS using at most one reactant, one inhibitors, and two products in each reaction.

Joint research with A.E. Porreca and G. Rozenberg.

Reaction systems, transition systems, and equivalences
Maciej Koutny, Newcastle, UK

Reaction systems originated as a formal model for processes inspired by the functioning of the living cell. The underlying idea of this model is that the functioning of the living cell is determined by the interactions of biochemical reactions and these interactions are based on the mechanisms of facilitation and inhibition. Since their inception, reaction systems became a well-investigated novel model of computation. Following this line of research, we discuss a systematic framework for investigating a whole range of equivalence notions for reaction systems. Some of the equivalences are defined directly on reaction systems while some are defined through transition systems associated with reaction systems. In this way we establish a new bridge between reaction systems and transition systems. In order to define equivalences which capture various ways of interacting with an environment, we also introduce models of the environment which evolve in a finite-state fashion.

Joint research with J. Kleijn, Ł. Mikulski and G. Rozenberg.

Graph Representation of Equivalent Reaction Systems
Hendrik Jan Hoogeboom, Leiden, The Netherlands

Abstract. Reaction systems, introduced by Ehrenfeucht and Rozenberg, can be conveniently represented by graphs called zero-context graphs. When all possible contexts are considered, a zerocontext graph can be extended to a global transition graph. Two reaction systems are considered equivalent if and only if their global transition graphs are isomorphic. This talk discusses operations on zero-context graphs that lead to equivalent reaction systems. Related combinatorial results will be included.

Joint research with D. Genova and N. Jonoska.

Shapes of dependencies in reaction systems
Antonio E. Porreca, Marseille, France

We begin an analysis of the structures found in dependency graphs of reaction systems, and how they give rise to certain dynamical behaviours in their state transition diagrams. Here we focus on self-sustaining, non self-inhibiting cycles of reactions, which give rise to cycles of related length in the dynamics, and more complex structures of cycles all sharing a single point (flowers) or pairwise sharing a point (chains), which generate fixed points when at least two cycles have coprime lengths.

Joint research with L. Manzoni and G. Rozenberg.

Computation Graphs for Reaction Systems
Dirk Janssens, Antwerp, Belgium

Computation graphs provide a partial order semantics for (node rewriting) graph rewriting systems. Basically a computation graph is a DAG where nodes represent the nodes that occur in the graphs of a derivation, and edges represent the direct causality relationship between those nodes. The edges carry additional information (labels) describing the precise way graphs are transformed. Thus the approach is different from most work on partial order semantics, where nodes represent events: here they represent data elements. We apply this idea to reaction systems with a particular interest in composition and modularity. As a computation of a network of reaction systems can be described by the composition of computations of the component systems we get an insight in the choices that can be made in specifying such network, e.g. with respect to its synchronous or asynchronous operation. By fixing one component and considering the others as a context we get a way of defining useful abstractions and equivalences.

Joint research with G. Rozenberg.

Modeling Reaction Systems by Forbidding and Enforcing
Daniela Genova, Jacksonville, Florida, USA

Forbidding-Enforcing Systems (fe-systems) were introduced by Ehrenfeucht and Rozenberg as a way to define families of languages based on two sets of boundary conditions. They were motivated by molecular reactions and can model inhibition through a set of forbidding constraints and facilitation through a set of enforcing constraints. Different variants of fe-systems have been proposed in the context of formal languages, words, graphs, membrane systems, and more. Both reaction systems and fe-systems are qualitative models that abstract inhibition and facilitation. In some sense, fe-systems are the precursor of reaction systems. This talk will focus on modeling reaction systems through fe-systems, where forbidding sets are used to model the restrictions imposed by the inhibition constraints and reactants and products are modeled by enforcing sets.

Distributed Reaction Automata
Erzsébet Csuhaj-Varjú, Budapest, Hungary

Reaction automata are language acceptors which combine certain properties of classical automata and reaction systems, models for describing the interactive behaviour of biochemical reactions. Roughly speaking, a reaction automaton consists of two main components: the input string and an extended variant of reaction systems. In this case, the reaction is defined over finite multisets and the reaction system can be considered as a multiset rewriting system. After consuming an input symbol, the reaction system performs reactions, according to its working mode. A string is accepted by a reaction automaton if it is consumed and the interactive process ultimately converges (stabilizes) on some multiset. In this talk we introduce the notion of a distributed system of reaction automata or also called distributed reaction automata (DRA), a concept inspired by distibuted P automata in membrane computing. A DRA consists of an input string and a finite collection of reaction automata that interact with the input string and may interact with each other by exhanging multisets at their disposal. We define several working modes of these systems depending on different conditions: for example, how the input string is processed (for example, the string is a concatenation of strings accepted by the component reaction automata), how interactions between two components are performed. We present some results on the computational power of some DRA variants and demonstrate the efficiency of distributed reaction automata in parallelization of language acceptance processes

Embedding Reaction Systems into link-calculus
Linda Brodo, Sassari, Italy

In the area of Natural Computing, Reaction Systems are a computational abstraction inspired by the functioning of living cells, suitable to model the main mechanisms of biochemical reactions, but applicable as well to many other areas of research. Reaction Systems consist of rules that interact with the environment during a reaction, but not among themselves. In this extended abstract we consider a variant of the link-calculus, which allows to model multiparty interactions in concurrent systems, and show that it allows to faithfully embed Reaction Systems and can be used to explore several enhancements, e.g. with mutating entities or rules that exchange entities. In the full paper we prove the correctness and completeness of our embedding, and we present more complex examples.

Joint research with R. Bruni and M. Falaschi.

Temporal Logic for Chemical Exploration Systems
Wojciech Penczek, Warsaw, Poland

A. Ehrenfeucht and G. Rozenberg introduced in [1] the notion of an exploration system, which extended the concept of a reaction system by introducing so-called zoom structures, meant to formalize the body of knowledge for a certain branch of science. Exploration systems are built as complex partial order structure, which allows for expressing the relationships between various notions in a given discipline of science. Here we formalize a seminal example of a chemical exploration system given in [1] by giving a fully formal definition of first a chemical zoom structure, and then a chemical exploration system built on such a structure. Then we go on to define a Kripke-style model for a chemical zoom structure over a set of contexts, equipped with two types of transitions relations: a global one for moving between states of the system, and a local one for moving inside a state. This is necessary, for a state is a complex structure itself: namely, a set of maximum inzooms (reversed chains in a partial order). Finally, we define a temporal logic to be used for reasoning about the properties of chemical reaction system or proving them with a model checking technique. The temporal logic for exploration systems is an extension of the branching time logic rsCTL of [3].

Joint research with B. Konikowska.

What do we know (and what we don’t) about the computational complexity of reaction systems
Luca Manzoni, Milano, Italy and Antonio E. Porreca, Marseille, France

Reaction Systems (RS) can exhibit rich dynamical behaviours, such as fixed points, cycles of potentially exponential length, and long preperiods. It is then natural to ask ourself how this can be translated into computational complexity results, either in terms of detection of the dynamical behaviours expressed by a given RS, or how this can be exploited to perform computational tasks. We present a summary of the known computational complexity results and discuss what remains to investigate on RS as computaional devices, and their relations with other computational models.

Joint research with A. Dennunzio and E. Formenti.

Bringing Asynchrony to Reaction Systems
Alex Yakovlev, Newcastle, UK

Reaction systems have a number of underlining principles that govern them in their operation. They are: (i) maximum concurrency, (ii) complete renewal of state (no permanency), (iii) both promotion and inhibition, (iv) 0/1 (binary) resource availability, (v) no contention between resources. Most of these principles could be seen as constraints in a traditional asynchronous behaviour setting. However, under a certain viewpoint these principles do not contradict to principles underpinning asynchronous circuits if the latter were considered at an appropriate level of abstraction. Asynchrony typically allows enabled actions to execute in either order, retains the state of enabled actions while other actions are executed, involves fine grained causality between elementary events and permits arbitration for shared resources. This talk will discuss some of these potential controversies and attempt to show ways of resolving them and thereby bringing asynchrony into the realm of reaction systems. Besides that, we will also look at how the paradigm of reaction systems can be exploited in designing concurrent electronic systems.

Joint research with M. Koutny.

Transactions and contracts based on reaction systems
Paolo Bottoni, Roma, Italy

Smart contracts are becoming attractive, thanks to the infrastructure provided by blockchain-based technologies. However, their effective use requires that the textual (legalese) specification of the contract be accompanied by a precise computational definition of the admissible ordering of actions leading to satisfaction or breach of a contract, as well as of the actions themselves. As contracts can be typically viewed as prescribing transactional exchanges of well-specified resources allocated among well-specified actors, the execution of a contract can be modelled as following some protocol in a closed world. This suggests a modeling of such executions as processes of reaction systems, in which the entities in the background set represent possible allocations of resources to actors and reactions describe changes in such allocations. We present therefore a complete modelling of transactions and contracts in terms of processes of reaction systems and discuss several forms of equivalence among processes, whereby two processes are equivalent if, starting from the same initial configuration of allocations, they produce the same final configuration.

Joint research with A. Labella and G. Rozenberg.

Reaction systems with influence on environment
Anna Labella, Rome, Italy

The talk will report on a systematic investigation of possible interactions of a reaction system with its environment (context). While in the original definition this interaction is one-way, i.e., the behaviour of a reaction system is influenced by its environment, we consider that a system can in turn influence its environment, possibly in a delayed manner. The behaviour of reaction systems when such a two-way interaction takes place is characterised by first establishing its relationship to their context-independent behaviour (i.e., the behaviour which is not influenced by the environment) and then discussing how to model such behaviour through context-independent processes of reaction systems which are suitable extensions of the original one.

Joint research with P.Bottoni and G. Rozenberg.

Rough sets and reaction systems
Andrzej Skowron, Warsaw, Poland

We discuss two approaches towards modeling of complex phenomena. The first one is based on constructing simplified models of complex phenomena, deriving properties from the models, and verifying those properties experimentally. This approach works when objects related to phenomena can be separated from interactions with the environment. Such models of phenomena are available in the existing literature. But when these interactions are significant for the phenomena, i.e., the future states of objects are difficult to determine in isolation with the environmental impact, and they co-depend on the states of those which are interacting with them, then the first approach does not work. The second approach aims to overcome this difficulty by developing models based on perception and actions, in the context of interference of unpredictable interactions with the environment. These models are adaptively evolving using the perceived information and experience. The models, which are learned from data, are in the form of complex networks evolving with time. Their changes are dependent on rough set based approximations of complex vague concepts used to initiate (or terminate) actions. We also emphasize the role of reasoning, called judgment, about computations realized by such models which are used to control computations on complex granules. It is worthwhile to recall here the meaning of wisdom as rightly judging. Some relationships between the discussed approaches are outlined. For example, the second approach can be used for verifying the models (e.g., of reaction systems) developed on the basis of the first approach. It can help to discover constraints under which such models are valid, and to discover strategies for adaptation of models, or explain the role of zoom structures in perception of situations.

Joint research with S. Dutta, A. Jankowski and G. Rozenberg.