Abstract

We define the jump complexity of a finite automaton with translucent letters as a function that computes the smallest upper bound on the number of jumps needed by the automaton in order to accept each word of length n, for any positive integer n. We prove that a sufficient condition for a finite automaton with translucent letters to accept a regular language is to have a jump complexity bounded by a constant. Along the same lines, we show that there are languages which require a jump complexity in Omega(n) of any finite automaton with translucent letters accepting one of these languages. We also show that there exist nondeterministic finite automata with translucent letters of jump complexity in O(log n) and O(root n) that accept non-regular languages. Several open problems and directions for further developments are finally discussed.

Abstract

We consider networks whose nodes host splicing processors, that is processors that are able to simulate the DNA recombination by splicing. Several topologies for the underlying graph of these networks are investigated. More precisely, we show that each network of splicing processors with some underlying graph can be directly converted into an equivalent network having an underlying graph of a different topology. Several common topologies are considered: full-mesh, star, grid, and wheel (ring-star). We also investigate the time and size complexity of each of these simulations.

Abstract

We consider networks whose nodes host splicing processors, that is processors that are able to simulate the DNA recombination by splicing. Several topologies for the underlying graph of these networks are investigated. More precisely, we show that each network of splicing processors with some underlying graph can be directly converted into an equivalent network having an underlying graph of a different topology. Several common topologies are considered: full-mesh, star, grid, and wheel (ring-star). We also investigate the time and size complexity of each of these simulations. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Abstract

Motivated by the need of reducing the huge amount of data navigating simultaneously through a network of polarized splicing processors, we look to the possibility of introducing probabilities which theoretically could decrease this amount, at a price of some loss of certainty. We imagined two possible situations regarding the splicing step: to associate either fixed or dynamically computed probabilities with splicing rules in every node. Similarly to the splicing step, two situations could be considered for the communication step depending on the way the probabilities are associated: statically or dynamically. We believe that this new feature together with the communication protocol based on polarization might facilitate software simulations or hardware implementations. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Abstract

We propose a simulation of an arbitrary network of evolutionary processors by a network having a special underlying graph, namely a wheel (ring-star) graph. This work continues a series of papers devoted to simulations between networks of evolutionary processors with various topologies. Somehow unexpected, the simulation is time complexity preserving at the price of a much larger network.

Abstract

Networks of splicing processors are one of the theoretical computational models that take inspiration from nature to efficiently solve problems that our current computational knowledge is not able to. One of the issues restricting/hindering is practical implementation is the arbitrariness of the underlying graph, since our computational systems usually conform to a predefined topology. We propose simulations of networks of splicing processors having arbitrary underlying graphs by networks whose underlying graphs are of a predefined topology: complete, star, and grid graphs. We show that all of these simulations are time efficient in the meaning that they preserve the time complexity of the original network: each computational step in that network is simulated by a fixed number of computational steps in the new topologic networks. Moreover, these simulations do not modify the order of magnitude of the network size.

Abstract

This work is a survey of the main results reported for the degree of extension of two models defining non-regular languages, namely the context-free grammar and the extended automaton over groups. More precisely, we recall the main results regarding the degree on non-regularity of a context-free grammar as well as the degree of extension of finite automata over groups. Finally, we consider a similar measure for the finite automata with translucent letters and present some preliminary results. This measure could be considered for many mechanisms that extend a less expressive one. © V. Mitrana, M. Păun This work is licensed under the Creative Commons Attribution License.

Abstract

We continue here the theoretical study initiated approximately twenty years ago on the possibility of using living cells for computing. In this paper, we reconsider the formal operations inspired by the intramolecular DNA rearrangements in the evolution of the macronucleus from the micronucleus in a group of ciliates. After introducing the concept of a valid string, we propose an efficient algorithm for checking this property for a given string. Then we investigate which of the considered operations preserve the property of a string to be valid. We also show that just one of the operations can be simulated by a finite transducer. The important problem regarding the order of applying the operations is then investigated showing that one operation can commute with the other two. Finally, we introduce the iterated variants and investigate a few properties. A sort of a normal form for the gene assembly in ciliates is obtained. The paper ends by a short discussion about open problems and further directions of research.

Abstract

Networks of evolutionary processors (NEP for short) form a class of models within the new computational paradigms inspired by biological phenomena. They are known to be theoretically capable of solving intractable problems. So far, there are two main categories that differ from each other by the nature of filtering process controlling the communication step: random-context clauses or polarization. Several studies have proven that both of them are computationally complete through efficient simulations of universal computational models such as Turing machines and 2-tag systems. Nevertheless, the indirect conversion between the two network variants results in an exponential increase of the computational complexity. In this paper, we suggest a direct simulation of polarized NEP through NEP with random-context filters which incurs in lower complexity costs.

Abstract

We introduce an accepting splicing system based on a type of splicing, multiple splicing, which has never considered so far for accepting systems. This type of splicing differs from the usual operation in that several (not necessarily distinct) rules can be applied simultaneously to the same string. We first consider accepting multiple splicing systems where the number of splicing sites is a predefined constant. We prove that this model is computationally complete, if the constant is 2, by simulating a 2-tag system. Moreover, we show that the simulation is time-complexity preserving, and discuss also the descriptional complexity of the accepting splicing system given by our construction. We then consider the accepting multiple splicing systems where the number of sites has either an upper bound or a lower bound. The computational power of these systems is also investigated. We finally discuss some open problems. (C) 2022 The Author(s). Published by Elsevier B.V. on behalf of King Saud University.

Abstract

Networks of splicing processors (NSP for short) embody a subcategory among the new computational models inspired by natural phenomena with theoretical potential to handle unsolvable problems efficiently. Current literature considers three variants in the context of networks managed by random-context filters. Despite the divergences on system complexity and control degree over the filters, the three variants were proved to hold the same computational power through the simulations of two computationally complete systems: Turing machines and 2-tag systems. However, the conversion between the three models by means of a Turing machine is unattainable because of the huge computational costs incurred. This research paper addresses this issue with the proposal of direct and efficient simulations between the aforementioned paradigms. The information about the nodes and edges (i.e., splicing rules, random-context filters, and connections between nodes) composing any network of splicing processors belonging to one of the three categories is used to design equivalent networks working under the other two models. We demonstrate that these new networks are able to replicate any computational step performed by the original network in a constant number of computational steps and, consequently, we prove that any outcome achieved by the original architecture can be accomplished by the constructed architectures without worsening the time complexity.

Abstract

In this paper, we propose direct simulations between a given network of evolutionary processors with an arbitrary topology of the underlying graph and a network of evolutionary processors with underlying graphs-that is, a complete graph, a star graph and a grid graph, respectively. All of these simulations are time complexity preserving-namely, each computational step in the given network is simulated by a constant number of computational steps in the constructed network. These results might be used to efficiently convert a solution of a problem based on networks of evolutionary processors provided that the underlying graph of the solution is not desired.

Abstract

This paper is part of the investigation of some operations on words and languages with motivations coming from DNA biochemistry, namely three variants of hairpin completion and three variants of hairpin reduction. Since not all the hairpin completions or reductions of semilinear languages remain semilinear, we study sufficient conditions for semilinear languages to preserve their semilinearity property after applying the non-iterated hairpin completion or hairpin reduction. A similar approach is then applied to the iterated variants of these operations. Along these lines, we define the hairpin reduction root of a language and show that the hairpin reduction root of a semilinear language is not necessarily semilinear except the universal language. A few open problems are finally discussed.

Abstract

We define and investigate a complexity measure defined for extended finite automata over groups (EFA). Roughly, an EFA is a finite automaton augmented with a register storing an element of a group, initially the identity element. When a transition is performed, not only the state, but the register contents are updated. A word is accepted if, after reading completely the word, the automaton reached a final state, and the register returned to the identity element. The group memory complexity of an EFA over a group is a function from N to N which associates with each n the value 0, if there is no word of length n accepted by the automaton, or the minimal integer c such that for every word x of length n accepted by the automaton, there is a computation on x such that the number of transitions labeled by non-neutral element of the group used in that computation is at most c. We prove that a language is regular if and only if it is accepted by an EFA with a finite group memory complexity. In particular, any EFA over a group such that all its finitely generated subgroups are finite accepts a regular language. We then provide examples of EFA over some groups that accept non-regular languages and have a sublinear group memory complexity, namely a function in O(root n) or O(log n). There are non-regular languages such that any EFA over some group that accepts that language has a group memory complexity in Omega(n). (C) 2020 Elsevier Inc. All rights reserved.

Abstract

We investigated the computational power of a new variant of network of splicing processors, which simplifies the general model such that filters remain associated with nodes but the input and output filters of every node coincide. This variant, callednetwork of uniform splicing processors, might be implemented more easily. Although the communication in the new variant seems less powerful, the new variant is sufficiently powerful to be computationally complete. Thus, nondeterministic Turing machines were simulated by networks of uniform splicing processors whose size depends linearly on the alphabet of the Turing machine. Furthermore, the simulation was time efficient. We argue that the network size can be decreased to a constant, namely six nodes. We further show that networks with only two nodes are able to simulate 2-tag systems. After these theoretical results, we discuss a possible software implementation of this model by proposing a conceptual architecture and describe all its components.

Abstract

This work is a survey of the most recent results regarding the computational power of the networks of bio-inspired processors whose communication is based on a new protocol called polarization. In the former models, the communication amongst processors is based on filters defined by some random-context conditions, namely the presence of some symbols and the absence of other symbols. In the new protocol discussed here, a polarization (negative, neutral, and positive) is associated with each node, while the polarization of data navigating through the network is computed in a dynamical way by means of a valuation function. Consequently, the protocol of communication amongst processors is naturally based on the compatibility between their polarization and the polarization of the data. We consider here three types of bio-inspired processors: evolutionary processors, splicing processors, and multiset processors. A quantitative generalization of polarization (evaluation sets) is also presented. We recall results regarding the computational power of these networks considered as accepting devices. Furthermore, a solution to an intractable problem, namely the 0 / 1 Knapsack problem, based on the networks of splicing processors with evaluation sets considered as problem solving devices, is also recalled. Finally, we discuss some open problems and possible directions for further research in this area.

Abstract

We propose a new variant of network of evolutionary picture processors, where the operations mask and unmask considered in [4] are replaced by the circular permutation of a row or column on the picture frontier. We propose a solution based on these networks to the picture pattern matching problem that runs in O(n + m + kl) computational steps, where the pattern is of size (k ,l) and the input picture is of size (n,m). We finally discuss how our solution may easily lead to solutions to a few further related problems on pictures.

Abstract

We define a variant of accepting splicing system that can be used as a problem solver. A condition for halting the computation on a given input as well as a condition for making a decision as soon as the computation has stopped is considered. An algorithm based on this accepting splicing system that solves a well-known NP-complete problem, namely the 3-colorability problem is presented. We discuss an efficient solution in terms of running time and additional resources (axioms, supplementary symbols, number of splicing rules. More precisely, for a given graph with n vertices and m edges, our solution runs in O (nm) time, and needs O (mn(2)) other resources. Two variants of this algorithm of a reduced time complexity at an exponential increase of the other resources are finally discussed.

Abstract

Abstract

An intriguing problem in computer science is the formal description of dynamics in cell populations. We propose here a multi-agent-based model that could be used in this respect. The model proposed in this paper consists of biological entities (cells) as agents and a biochemical environment. Both are represented by multisets of symbols. The environment evolution is regulated by multiset Lindenmayer rules depending on the current state of all agents, while the evolution of each agent, which depends on the environment current state, is defined by means of multiset patterns. We discuss some algorithmic problems related to the dynamics of the proposed multi-agent model: infinite and stationary evolution, environment, and agent reachability.

Abstract

We continue the investigation of three operations on words and languages with motivations coming from DNA biochemistry, namely unbounded and bounded hairpin completion and hairpin lengthening. We first show that each of these operations can be used for replacing the third step, the most laborious one, of the solution to the CNF-SAT reported in [28]. As not all the bounded/unbounded hairpin completion or lengthening of semilinear languages remain semilinear, we study sufficient conditions for semilinear languages to preserve their semilinearity property after applying once either the bounded or unbounded hairpin completion, or lengthening. A similar approach is then started for the iterated variants of the three operations. A few open problems are finally discussed.

Abstract

In this paper, we consider the computational power of a new variant of networks of splicing processors in which each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined (negative, neutral, positive), the polarization of data is dynamically computed by means of a valuation mapping. Consequently, the protocol of communication is naturally defined by means of this polarization. We show that networks of polarized splicing processors (NPSP) of size 2 are computationally complete, which immediately settles the question of designing computationally complete NPSPs of minimal size. With two more nodes we can simulate every nondeterministic Turing machine without increasing the time complexity. Particularly, we prove that NPSP of size 4 can accept all languages in NP in polynomial time. Furthermore, another computational model that is universal, namely the 2-tag system, can be simulated by NPSP of size 3 preserving the time complexity. All these results can be obtained with NPSPs with valuations in the set as well. We finally show that Turing machines can simulate a variant of NPSPs and discuss the time complexity of this simulation.

Abstract

Abstract

Abstract

This paper presents the latest trends and approaches used for constructing nanoscale structures of 2D objects through DNA folding based on the DNA origami technology developed by Rothemund. The Rothemund method has been used in the construction of various shapes, such as the development of the nanoscale structure for the United States map. Following the steps of Rothemund's technique, we simulate the construction of the Romanian map nanoscale 2D structure, embedding the number 100 into it.

Abstract

The aim of this paper is to discuss two possible ways of introducing some features based on probabilistic concepts and methods in networks of polarized evolutionary processors (NPEP). We associate probabilities with rules in every node such that together with the communication protocol, which is based on the compatibility between the polarization of each node and data navigating through the network, might facilitate the study of biological phenomena as well as software simulations or hardware implementations. The probability associated with rules may be a priori defined and fixed or may be computed dynamically. Probabilities will also appear when communicating data between nodes; these probabilities may be statically or dynamically defined. This note also proposes the study of the impact of these characteristics and see how these new features reduce the gap between the formal model and its practical applicability. Introducing probabilities in NPEP is aimed to decrease the exponential expansion of the number of strings which appear in the computations used to solve NP-problems in a polynomial time. A decreasing of the exponential expansion of this number is achieved with a loss of certainty of the final result which is reached with some error probability.

Abstract

In this paper, we consider the computational power of a new variant of networks of splicing processors in which each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined (negative, neutral, positive), the polarization of data is dynamically computed by means of a valuation mapping. Consequently, the protocol of communication is naturally defined by means of this polarization. We show that networks of polarized splicing processors (NPSP) of size 2 are computationally complete, which immediately settles the question of designing computationally complete NPSPs of minimal size. We prove that NPSP of size 4 can accept all languages in NP in polynomial time. All these results can be obtained with NPSPs with valuations in the set {-1, 0, 1} as well. We finally show that Turing machines can simulate a variant of NPSPs and discuss the time complexity of these simulations.