The concept of LL( k ) context-free grammars is extended to cooperating distributed (CD) grammar systems working in the = m -mode of derivation in a consistent way. Namely, every LL( k ) context-free language can be generated by an LL( k ) CD grammar system. Further fundamental properties of languages generated by LL( k ) CD grammar systems are proved, for instance their unambiguity and the capability of LL( k ) CD grammar systems to describe typical non-context-free languages, including even a non-semilinear language. Most importantly, a parsing algorithm with strictly sub-quadratic time complexity is presented for LL( k ) CD grammar systems.

Abstract We investigate the relationship of languages characterized by variants of string assembling systems and by Watson-Crick finite automata with a small number of states. Besides the general variant, we consider so-called free, and pure string assembling systems and compare their language generating power to Watson-Crick finite automata having one state (also called stateless) and two or three states in their state sets. We also study restricted variants of models that describe unary languages.

Abstract We continue the investigation of the computational power of non-cooperative polymorphic P systems with no ingredients (no target indicators or any special features added to the rules) in terms of parallel communicating Lindenmayer systems. We precisely characterize the language class generated by these types of P systems using a restricted class of parallel communicating ET0L systems. Our results demonstrate that the dynamically changing rewriting rules provided by the polymorphic framework in non-cooperating P systems results in a similar increase in computational power as a restricted variant of the parallel communicating framework does in the power of ET0L systems.

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.

We study the reversibility of communicating reaction systems, variants of networks of reaction systems communicating by sending reaction products to specific target components. We first consider the possibility of “backtracking” their computations, then define distributed communicating reaction systems, an “unsynchronized” variant of the model in order to show how reversibility can be defined in a causally consistent manner.

Abstract We study the concept of reversibility in connection with parallel communicating systems of finite automata (PCFA in short). We define the notion of reversibility in the case of PCFA (also covering the non-deterministic case) and discuss the relationship of the reversibility of the systems and the reversibility of its components. We show that a system can be reversible with non-reversible components, and the other way around, the reversibility of the components does not necessarily imply the reversibility of the system as a whole. We also investigate the computational power of deterministic centralized reversible PCFA. We show that these very simple types of PCFA (returning or non-returning) can recognize regular languages which cannot be accepted by reversible (deterministic) finite automata, and that they can even accept languages that are not context-free. We also separate the deterministic and non-deterministic variants in the case of systems with non-returning communication. We show that there are languages accepted by non-deterministic centralized PCFA, which cannot be recognized by any deterministic variant of the same type.

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.

Deterministic one-way Turing machines with sublinear space bounds are systematically studied. We distinguish among the notions of strong, weak, and restricted space bounds. The latter is motivated by the study of P automata. The space available on th

Membrane systems are nature motivated computational models inspired by certain basic features of biological cells and their membranes. They are examples of the chemical computational paradigm which describes computation in terms of chemical solutions

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.