Search

Reaction systems are a model of computing aiming to formalize biochemistry by capturing the qualitative relations between the species, and explicitly discarding any accounts of multiplicity. From the point of view of the formal language theory, this situates them in the realm of set rewriting. In this work, we propose a series of extensions of reaction systems to use strings. These extensions form a spectrum in the sense that all of them honor the hallmark features of the original model: the threshold principle and the non-permanency principle. We thoroughly discuss the details of the structure and the behavior of these variants, and commence studying their expressive power by comparing them to some classic models of computing. [ABSTRACT FROM AUTHOR]

This work introduces the new class of pure reaction automata, as well as a new update manner, called maximal reactive manner, that can also be applied to standard reaction automata. Pure reaction automata differ from the standard model in that they don't have permanence: the entities that are not consumed by the reactions happening at a certain state are not conserved in the result states. We prove that the set of languages accepted by the new class under the maximal reactive manner contains the set of languages accepted by standard reaction automata under the same manner or under the maximal parallel manner. We also prove that a strict subclass of pure reaction automata can compute any partial recursive function. [ABSTRACT FROM AUTHOR]

To determine the computational capacity of cellular automata they are often investigated towards their ability to accept formal languages within certain time constraints. In this paper, we take up an opposite position and look at cellular automata towards their ability to generate patterns, within certain time constraints. As an example we describe a construction of a cellular automaton that generates prefixes of the Oldenburger–Kolakoski sequence within real time. Furthermore, we study the real-time generation of unary and non-unary patterns in depth. In the unary case, we obtain a characterization by time-constructible functions and their corresponding unary formal languages. In the non-unary case, we provide constructions that generate any arbitrary given properly thin context-free language as well as all prefixes of any given automatic sequence. [ABSTRACT FROM AUTHOR]

This paper introduces conjugate word blending as a formal model of molecular processes that occur during a DNA experimental protocol called cross-pairing Polymerase Chain Reaction (XPCR). We analyze this formal word and language operation from a computational viewpoint, by investigating closure properties of four Chomsky language families under it. We also report the molecular biology wet lab experiments based on XPCR amplification of gene sequences, which led to the notion of conjugate word blending. [ABSTRACT FROM AUTHOR]

Geometric folding processes are ubiquitous in natural systems ranging from protein biochemistry to patterns of insect wings and leaves. In a previous study, a folding operation between strings of formal languages was introduced as a model of such processes. The operation was then used to define a folding system (F-system) as a construct consisting of a core language, containing the strings to be folded, and a folding procedure language, which defines how the folding is done. This paper reviews main definitions associated with F-systems and next it determines necessary conditions for a language to belong to classes generated by such systems. The conditions are stated in the form of pumping lemmas and four classes are considered, in which the core and folding procedure languages are both regular, one of them is regular and the other context-free, or both are context-free. Full demonstrations of the lemmas are provided, and the analysis is illustrated with examples. [ABSTRACT FROM AUTHOR]

Insertion–deletion (or ins–del for short) systems are simple models of bio-inspired computing. They are well studied in formal language theory, especially regarding their computational completeness. This concerns the question if all recursively enumerable languages can be generated. This ultimately addresses the question if one can build general-purpose computers rooted in this formalism. The descriptional complexity of an ins–del system is typically measured by its size, a 6-dimensional tuple of non-negative integers (e , e ′ , e ′ ′ ; d , d ′ , d ′ ′) where e is the maximum length of the insertion string, e ′ (and e ′ ′ ) is the maximum length of the left (and right) context used for insertion; the last three parameters d , d ′ , d ′ ′ are similarly understood for deletion rules. Computational completeness for ins–del systems can even be achieved with rule size (1, 1, 1; 1, 1, 1) but with no rule size strictly smaller than this. This fact has motivated to study ins–del systems in combination with regulation mechanisms. In this context, the six-tuple explained above is called the ID size of a system. Several regulations like graph-control, matrix and semi-conditional have been imposed on ins–del systems. Typically, the computational completeness results are obtained as trade-offs, reducing the ID size, say, to (1, 1, 0; 1, 1, 0) at the expense of increasing other measures of descriptional complexity. In this paper, we study simple semi-conditional ins–del systems, where an ins–del rule can be applied only in the presence or absence of substrings of the derivation string. This brings along two further natural parameters to measure descriptional complexity, namely, the maximum permitting string length p and the maximum forbidden string length f, usually summarized as the degree d = (p , f) . We show that simple semi-conditional ins–del systems of degree (2, 1) and with ID sizes (1 + e , e ′ , e ′ ′ ; 1 + d , d ′ , d ′ ′) are computationally complete for any e , e ′ , e ′ ′ , d , d ′ , d ′ ′ ∈ { 0 , 1 } , with e + e ′ + e ′ ′ = 1 and d + d ′ + d ′ ′ = 1 . The obtained results complement and improve on the existing results known from the literature. To prove our results, we also show a new normal form for type-0 grammars that appears to be interesting in its own right. [ABSTRACT FROM AUTHOR]

We present general results that are useful in showing closure and decidable properties of large classes of languages with respect to biologically-inspired operations. We use these results to prove new decidability results and closure properties of some classes of languages under bio-operations such hairpin-inversion, the recently studied operation of pseudo-inversion, and other bio-operations. We also provide techniques for proving undecidability results. In particular, we give a new approach for proving the undecidability of problems for which the usual method of reduction to the undecidability of the Post Correspondence Problem seems hard to apply. Our closure and decidability results strengthen or generalize previous results. [ABSTRACT FROM AUTHOR]

We consider a pseudo-inversion operation inspired by biological events, such as DNA sequence transformations, where only parts of a string are reversed. We define the pseudo-inversion of a string $$w = uxv$$ to be the set of all strings $$v^Rxu^R$$ , where $$uv \ne \lambda $$ and consider the operation from a formal language theoretic viewpoint. We show that regular languages are closed under the pseudo-inversion operation whereas context-free languages are not. Furthermore, we study the iterated pseudo-inversion operation and show that the iterated pseudo-inversion of a context-free language is recognized by a nondeterministic reversal-bounded multicounter machine. Finally, we introduce the notion of pseudo-inversion-freeness and examine closure properties and decidability problems for regular and context-free languages. We demonstrate that pseudo-inversion-freeness is decidable in polynomial time for regular languages and undecidable for context-free languages. [ABSTRACT FROM AUTHOR]

Previous work by Demaine et al. (Nat Comput 6937:100-114, ) developed a strong connection between smallest context-free grammars and staged self-assembly systems for one-dimensional strings and assemblies. We extend this work to two-dimensional polyominoes and assemblies, comparing staged self-assembly systems to a natural generalization of context-free grammars we call polyomino context-free grammars (PCFGs). We achieve nearly optimal bounds on the largest ratios of the smallest PCFG and staged self-assembly system for a given polyomino with $$n$$ cells. For the ratio of PCFGs over assembly systems, we show that the smallest PCFG can be an $$\varOmega (n/\log ^3{n})$$ -factor larger than the smallest staged assembly system, even when restricted to square polyominoes. For the ratio of assembly systems over PCFGs, we show that the smallest staged assembly system is never more than a $$O(\log {n})$$ -factor larger than the smallest PCFG and is sometimes an $$\varOmega (\log {n}/\log \log {n})$$ -factor larger. [ABSTRACT FROM AUTHOR]

We describe an algorithm which automates the generation of appropriate shift and coin operators for a discrete time quantum walk, given the adjacency matrix of the graph over which the walk is run. This gives researchers the freedom to numerically investigate any discrete time quantum walk over graphs of a computationally tractable size by greatly reducing the time required to initialise a given walk. We then describe one application in which the swift initialisation of walks has enabled systematic investigations of walks over a large number of structures. New results concerning this application, which is to formal language recognition, are described. The reliability of these results, as well as the general suitability of numerical analysis as a tool for investigating discrete time quantum walks, are briefly discussed. We also mention specific Python packages which facilitate our simulations and analysis, motivating the use of high level programming languages in this context. [ABSTRACT FROM AUTHOR]

Watson-Crick Lindenmayer systems add a control mechanism to ordinary Lindenmayer (L) system derivations. The mechanism is inspired by the complementarity relation in DNA strings, and it is formally defined in terms of a trigger language (trigger, for short). It is known that Watson-Crick E0L systems employed with the standard trigger (which is a context-free language) are computationally universal. Here we show that all recursively enumerable languages can be generated already by a Uni-Transitional Watson-Crick E0L system with a regular trigger. A system is Uni-Transitional if any derivation of a terminal word can apply the Watson-Crick morphism at most once. We introduce a weak derivation mode where, for sentential forms in the trigger language, the derivation chooses nondeterministically whether or not to apply the Watson-Crick morphism. We show that Watson-Crick E0L systems employing a regular trigger and the weak derivation mode remain computationally universal but, on the other hand, the corresponding Uni-Transitional systems generate only a subclass of the ET0L languages. We consider also the computational power of Watson-Crick (deterministic) ET0L systems. [ABSTRACT FROM AUTHOR]

This paper is placed in a formal framework in which the interdisciplinary study of natural language is conducted by integrating linguistics, computer science and biology. It provides an overview of the field of research, conveying the main biological ideas that have influenced research in linguistics. Our work highlights the main methods of molecular computing that have been applied to the processing and study of the structure of natural language: DNA computing, membrane computing and networks of evolutionary processors. Moreover, some new challenges and lines of research for the future are pointed out, that can provide important improvements in the understanding of natural language as a structure and a human capacity. [ABSTRACT FROM AUTHOR]

Transposable genetic elements are prevalent across many living organisms from bacteria to large mammals. Given the linear primary structure of genetic material, this process is natural to study from a theoretical perspective using formal language theory. We abstract the process of genetic transposition to operations on languages and study it combinatorially and computationally. It is shown that the power of such systems is large relative to the classic Chomsky Hierarchy. However, we are still able to algorithmically determine whether or not a string is a possible product of the iterated application of the operations. [ABSTRACT FROM AUTHOR]

This article investigates insertion-deletion systems of small size, where at most two symbols can be used in the description of insertion or deletion rules in a context-free or contextual manner. The basic result shows a characterization by context-free grammars of insertion-deletion systems, which insert or delete one symbol in one symbol left context (systems of size (1, 1, 0; 1, 1, 0)). If context-free insertion or deletion rules are considered (systems of size (2, 0, 0; 1, 1, 0) or (1, 1, 0; 2, 0, 0)), then we show that corresponding systems are not computationally complete. However, if the insertion and the deletion operations having same size as above are considered in the distributed framework of P systems, then the computational power strictly increases and the obtained models become computationally complete. The article also shows that if context-free insertion and deletion rules of two symbols (of size (2, 0, 0; 2, 0, 0)) are used in combination with P systems, then the obtained model is still not computationally complete. Finally some open problems are presented. [ABSTRACT FROM AUTHOR]

Circular splicing has been introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we focus on the relationship between regular circular languages and languages generated by finite circular splicing systems. We survey the known results towards a characterization of the intersection between these two classes and provide new contributions on the open problem of finding this characterization. First, we exhibit a non-regular circular language generated by a circular simple system thus disproving a known result in this area. Then we give new results related to a restrictive class of circular splicing systems, the marked systems. Precisely, we review in a graph theoretical setting the recently obtained characterization of marked systems generating regular circular languages. In particular, we define a slight variant of marked systems, that is the g-marked systems, and we introduce the graph associated with a g-marked system. We show that a g-marked system generates a regular circular language if and only if its associated graph is a cograph. Furthermore, we prove that the class of g-marked systems generating regular circular languages is closed under a complement operation applied to systems. We also prove that marked systems with self-splicing generate only regular circular languages. [ABSTRACT FROM AUTHOR]

The translation of a messenger RNA into a functional protein is one of the most fundamental molecular processes in a cell. Groups of three ribonucleotides, called codons, uniquely specify amino acids to be used in the construction of a protein. When the translation process skips a number of bases it is possible for the reading frame of the RNA to be shifted. By making use of multiple reading frames, organisms and viruses are able to encode multiple proteins in a single gene. We propose here a formal model of these frameshifting events and investigate its basic mathematical properties and their relevance to biological systems. In addition, multiple time-efficient algorithms are created for use in the study of frameshifting. Some of these algorithms are created to work in general, for any type of frameshifting which could be found in organisms, while others are optimized for known specialized types of frameshifting. [ABSTRACT FROM AUTHOR]