# Victor Mitrana

## CS I - Bioinformatică

## Publicatii

Publication | Authors | Date | |
---|---|---|---|

article
## Networks Of Splicing Processors: Simulations Between Topologies |
Sanchez Martin Jose Angel; Mitrana Victor; Paun Mihaela | Journal Of Membrane Computing, 2023 | |

## AbstractNetworks 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. |
|||

conference
## On The Degree Of Extension Of Some Models Defining Non-Regular Languages |
Mitrana V.; Păun M. | Electronic Proceedings In Theoretical Computer Science, Eptcs, 2023 | |

## AbstractThis 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. |
|||

article
## Simulating Polarization By Random Context Filters In Networks Of Evolutionary Processors |
Mitrana Victor; Sanchez Martin Jose Angel | Journal Of Applied Mathematics And Computing, 2022 | |

## AbstractNetworks 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. |
|||

article
## Accepting Multiple Splicing Systems |
Sanchez Couso Jose Ramon; Arroyo Fernando; Mitrana Victor; Paun Andrei; Paun Mihaela | Journal Of King Saud University-Computer And Information Sciences, 2022 | |

## AbstractWe 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. |
|||

article
## Simulations Between Three Types Of Networks Of Splicing Processors |
Sanchez Couso Jose Ramon; Sanchez Martin Jose Angel; Mitrana Victor; Paun Mihaela | Mathematics, 2021 | |

## AbstractNetworks 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. |
|||

article
## Simulations Between Network Topologies In Networks Of Evolutionary Processors |
Sanchez Martin Jose Angel; Mitrana Victor | Axioms, 2021 | |

## AbstractIn 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. |
|||

article
## Hairpin Completions And Reductions: Semilinearity Properties |
Bordihn Henning; Mitrana Victor; Paun Andrei; Paun Mihaela | Natural Computing, 2021 | |

## AbstractThis 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. |
|||

article
## On The Group Memory Complexity Of Extended Finite Automata Over Groups |
Arroyo Fernando; Mitrana Victor; Paun Andrei; Paun Mihaela; Sanchez Couso Jose Ramon | Journal Of Logical And Algebraic Methods In Programming, 2020 | |

## AbstractWe 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. |
|||

article
## Networks Of Uniform Splicing Processors: Computational Power And Simulation |
Gomez-Canaval Sandra; Mitrana Victor; Paun Mihaela; Sanchez Martin Jose Angel; Sanchez Couso Jose Ramon | Mathematics, 2020 | |

## AbstractWe 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. |
|||

conference
## A Multi-Agent Model For Cell Population |
Fernando Arroyo; Victor Mitrana; Andrei Păun; Mihaela Păun | Agents And Multi-Agent Systems: Technologies And Applications 2019, Smart Innovation, Systems And Technologies (Book Series), 2019 | |

## AbstractAn 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. |
|||

conference
## Further Properties Of Self-Assembly By Hairpin Formation |
Henning Bordihn; Victor Mitrana; Andrei Păun; Mihaela Păun | International Conference On Unconventional Computation And Natural Computation, Unconventional Computation And Natural Computation, Ucnc 2019, 2019 | |

## AbstractWe 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. |
|||

conference
## Dna Self-Assembly By Hairpin |
Victor Mitrana | 11Th International Workshop On Non-Classical Models Of Automata And Applications, Valencia, Spania, 2019 | |

## Abstract |
|||

article
## Polarization: A New Communication Protocol In Networks Of Bio-Inspired Processors |
Victor Mitrana | Journal Of Membrane Computing, 2019 | |

## AbstractThis 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. |
|||

article
## Networks Of Picture Processors With Circular Permutation |
Fernando Arroyo; Sandra Gomez; Victor Mitrana; José Ramón Sanchez | Proceedings Of The Romanian Academy Series A-Mathematics Physics Technical Sciences Information Science, Proceedings Of The Romanian Academy, Series A, 2019 | |

## AbstractWe 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. |
|||

conference
## How Complex Is To Solve A Hard Problem With Accepting Splicing Systems |
Victor Mitrana; Andrei Paun; Mihaela Paun | 4Th International Conference On Complexity, Future Information Systems And Risk, Crete, Greece, Proceedings Of The 4Th International Conference On Complexity, Future Information Systems And Risk (Complexis), 2019 | |

## AbstractWe 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. |
|||

conference
## Towards Probabilistic Networks Of Polarized Evolutionary Processors |
Fernando Arroyo ; Sandra Gomez-Canaval ; Victor Mitrana ; Mihaela Paun ; Jose Ramon Sanchez-Couso | International Conference On High Performance Computing & Simulation (Hpcs), Proceedings 2018 International Conference On High Performance Computing & Simulation (Hpcs), 2018 | |

## AbstractThe 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. |
|||

conference
## Dna-Guided Assembly Of Nanocellulose Meshes |
Alexandru Amărioarei; Gefry Barad; Eugen Czeizler; Ana-Maria Dobre; Corina Iţcuş; Victor Mitrana; Andrei Păun; Mihaela Păun; Frankie Spencer; Romică Trandafir; Iris Tuşa | International Conference On Theory And Practice Of Natural Computing, Tpnc 2018: Theory And Practice Of Natural Computing, 2018 | |

## Abstract |
|||

article
## Small Networks Of Polarized Splicing Processors Are Universal |
Henning Bordihn; Victor Mitrana; Maria C. Negru; Andrei Păun; Mihaela Păun | Natural Computing, 2018 | |

## AbstractIn 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. |
|||

article
## 3D Dna Origami Map Structure Simulation |
Itcus Corina; Amarioarei Alexandru; Czeizler Eugen; Dobre Ana-Maria; Mitrana Victor; Negre Florentina; Paun Andrei; Paun Mihaela; Sidoroff Manuela Elisabeta; Trandafir Romica; Tusa Iris | Romanian Journal Of Information Science And Technology, 2018 | |

## AbstractThis 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. |
|||

conference
## Greedy Algorithms For Computing The Genomic Distance By Translocation |
Victor Mitrana | Workshop 2018 Algonano: Metode Algoritmice Și Computaționale În Bio-Medicină Și Nanotehnologie, 2018 | |

## Abstract |
|||

conference
## Networks Of Polarized Splicing Processors |
Henning Bordihn; Victor Mitrana; Andrei Păun; Mihaela Păun | International Conference On Theory And Practice Of Natural Computing, Tpnc 2017: Theory And Practice Of Natural Computing, Theory And Practice Of Natural Computing, Tpnc 2017, 2017 | |

## AbstractIn 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. |