Abstract A distributed reaction system consists of a finite set of reaction systems that either interact with a common environment or interact with each other by communicating products or reactions. A reaction system is a well-known qualitative formal model of interactions between biochemical reactions. A reaction is a triplet of nonempty sets representing chemicals, called the set of reactants, the set of inhibitors, and the set of products. A reaction corresponds to a chemical reaction performed on a set of chemicals, and a reaction system is a finite nonempty set of reactions. In this paper, we examine two variants of distributed reaction systems. We introduce the notion of a distributed reaction system with communication by request (a qDRS for short), where sets of products are communicated between the component reaction systems by queries. First, we show that every qDRS can be represented by a reaction system. After that we compare distributed reaction systems with communication by request to extended distributed reaction systems (EDRSs), models that were introduced in a previous paper. We prove that extended distributed reaction systems, where a context automaton provides input for the component reaction systems, simulate distributed reaction systems with communication by request and distributed reaction systems with communication by request simulate special variants of extended distributed reaction systems. Furthermore, we assign languages to these two variants of distributed reaction systems. We prove that the class of agreement languages of extended distributed reaction systems is equal to the class of languages of nondeterministic multihead finite automata and the agreement language of every distributed reaction system with communication by request is an element of a certain subregular language class.

Watson-Crick D0L systems (WD0L systems) are augmented variants of D0L systems defined over a DNA-like alphabet, where each letter has a complementary letter and this relation is symmetric. WD0L systems operate under a control that is inspired by the well-known phenomenon of Watson-Crick complementarity of the double helix of DNA. Depending on a trigger, the standard D0L rewriting step is applied either to the string or to its complementary string. In this paper, we examine extended networks of standard Watson-Crick D0L systems (ENSWD0L systems) with a variant of incomplete communication. An NWD0L system is a finite set of WD0L systems defined over a common DNA-like alphabet and operating in a synchronized manner. After rewriting their own strings in the WD0L manner, they communicate copies of certain generated strings (the so-called good strings) to the other nodes. In some previous papers, it was shown that ENSWD0L systems are computationally complete, and their computational power does not change if the communicated string is a non-empty prefix (non-empty suffix) of the generated string. We strengthen the previous results, namely we show that ENSWD0L systems are computationally complete even if the communicated string is an arbitrary substring of the generated string.

Abstract In this paper, we study reversibility in sP colonies and in reaction systems. sP colony is a bio-inspired computational model formed from an environment and a finite set of agents. The current state of the environment is represented by a finite set of objects and the current state of the agent is given by a finite multiset of objects. By execution of a program from a set of programs associated with the agent, the agent can change the objects in its own state and possibly in the environment, too. Reaction systems are a bio-inspired computational model where reactants are transformed into products only if some inhibitors are not present. We define sP colonies without input influence and prove that to any reversible sP colony of such type an inverse sP colony can be constructed that performs inverse computation. In the second part of the paper, we show that the concept of a reversible reaction system and the notion of an inverse reaction system can be defined in a similar way, and partially reversible reaction systems can simulate reversible logic gates and reversible Turing machines.

P automata are accepting computing devices combining features of classical automata and membrane systems. In this paper we introduce P n-stack-automata, a restricted class of P automata that mimics the behaviour of n-stack automata. We show that for n = 1 these constructs describe the context-free language class and for n = 3 the class of quasi-realtime languages.

In this paper we establish a connection between two concepts of unconventional computing, namely Watson-Crick T0L systems (schemes) and red-green Turing machines or red-green register machines. Our research was inspired by the conceptual similarity of a mind change of a red-green Turing or register machine and of a turn to the complementary string in Watson-Crick T0L systems as well as by the fact that both red-green Turing or register machines and Watson-Crick T0L systems define infinite computations on finite inputs. We define language recognition for Watson-Crick T0L systems based on the infinite sequences they generate, and we show that the sets of (vectors of) natural numbers which can be recognized by so-called standard Watson-Crick T0L schemes (with a context-free trigger) include the sets recognized by red-green register machines (or red-green Turing machines). The obtained results imply that using Watson-Crick T0L schemes we may “go beyond Turing” as the red-green register machines and red-green Turing machines can do. Furthermore, we also show that for any deterministic Watson-Crick 0L scheme with a regular trigger the recognizability problem of a word is decidable.

In this paper we investigate the use of general topological spaces in connection with a generalised variant of membrane systems. We provide an approach which produces a fine grain description of local operations occurring simultaneously in sets of compartments of the system by restricting the interactions between objects. This restriction is given by open sets of a topology and multisets of objects associated with them, which dynamically change during the functioning of the system and which together define a notion of vicinity for the objects taking part in the interactions.

In this paper we introduce and study P colonies where the environment is given as a string. These constructs, called automaton-like P colonies or APCol systems, behave like automata: during functioning, the agents change their own states and process

Klaus Ambos-Spies, Arnold Beckmann, Erzsébet Csuhaj-Varjú, Benedikt Löwe; Computability in Europe 2009, Journal of Logic and Computation, Volume 23, Issue

We introduce and investigate blackhole pushdown automata, variants of pushdown automata, where a string can always be pushed to the pushdown, but only a given depth of the pushdown content is remembered (the rest of the pushdown content is either canceled or becomes inaccessible). We also study blackhole variants of regulated pushdown automata, where the automaton in some distinguished states checks the form of its pushdown content against a given control language. We present characterizations of several language families in terms of these constructs.

A formal framework for studying systems made up of a community of agents and their environment is proposed. The suggested model, technically based on the theory of formal grammars and called an eco-grammar system, captures some common features of ecological, economic, social, and collective robotic systems. The article contains an informal presentation as well as the formal definition of the model, presents some properties of variants of eco-grammar systems, and discusses the emergence of important lifelike features such as birth and death. Emphasis is put on results with relevance for artificial life. Some recent developments are also briefly reported.