Author name cluster

Sergey Verlan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers

1 author row

TCS Journal 2024 Journal Article

Universal enzymatic numerical P systems with small number of enzymatic rules

Jun Liu
Leiya Wang
Gexiang Zhang
Sergey Verlan
Ming Zhu

Enzymatic Numerical P Systems (ENPSs) are a model of membrane computing that is well-suited for the simulation of physical processes and that has been used for the design and the implementation of motion controllers for wheeled robots and flying drones. The ENPSs model has been proven to be Turing universal and the theoretical effort was focused on minimizing various descriptional complexity parameters. In this paper, we explore the minimum number of enzymatic rules needed to achieve universality in ENPSs, specifically focusing on the all-parallel derivation mode where all applicable rules are applied at the same time. We show that in the case of a linear restriction for production functions, the universality can be obtained using 21 enzymatic rules, substantially improving previously known results. If production functions are allowed to be polynomials of degree 2, we show that a single enzymatic rule is sufficient to achieve universality. To obtain these results, a new proof method is introduced based on the translation of ENPSs to systems of conditional recurrences.

Details DOI

TCS Journal 2023 Journal Article

Numerical networks of cells

Artiom Alhazov
Rudolf Freund
Sergiu Ivanov
Sergey Verlan

Numerical P systems (NPS) are a very particular class of P systems having important differences from most models in this area. The main particularity of the model is the usage of numerical variables whose values are shared among applicable rules, contrary to the concurrence for objects in the multiset for the traditional P systems case. In 2007, Freund and Verlan developed a formal framework for P systems to capture most of the essential features of P systems and to define their functioning in a formal way. Subsequent papers developed versions of this framework for the case of spiking neural P systems and P systems with dynamically evolving structure. These results permitted to obtain a different view on P systems giving a general framework to analyze, relate and extend different variants of P systems and other related models, like Petri nets or register machines. This paper aims to provide a similar generalization for the case of numerical P systems (NPS) and related variants like enzymatic or generalized NPS. We call the obtained model Numerical Networks of Cells (NNC). As in the case of the formal framework it allows to accurately describe NPS, as well as other types of P systems like those using fuzzy sets as computation support. Also, the new model generalizes other well-known models like Boolean networks or reaction systems and this can potentially help to bring bridges between P systems and these areas.

Details DOI

TCS Journal 2020 Journal Article

Universal insertion grammars of size two

Sergey Verlan
Henning Fernau
Lakshmanan Kuppusamy

In this paper, we show that pure insertion grammars of size 2 (i. e. , inserting two symbols in a left and right context, each consisting of two symbols) can characterize all recursively enumerable languages. This is achieved by either applying an inverse morphism and a weak coding, or a left (right) quotient with a regular L O C ( 2 ) language, or an intersection with a L O C ( 2 ) language and a weak coding. The obtained results improve the descriptional complexity of insertion grammars and complete the picture of known results on insertion-deletion systems that are motivated from the DNA computing area.

Details DOI

TCS Journal 2012 Journal Article

Matrix insertion–deletion systems

Ion Petre
Sergey Verlan

We investigate in this article the operations of insertion and deletion working in a matrix-controlled manner. We show that this allows to us strictly increase the computational power: in the case of systems that are not computationally complete (with total size equal to 4), the computational completeness can be obtained by introducing the matrix control and using only binary matrices.

Details DOI

TCS Journal 2011 Journal Article

Minimization strategies for maximally parallel multiset rewriting systems

Artiom Alhazov
Sergey Verlan

Maximally parallel multiset rewriting systems (MPMRS) give a convenient way to express relations between unstructured objects. The functioning of various computational devices may be expressed in terms of MPMRS (e. g. , register machines and many variants of P systems). In particular, this means that MPMRS are Turing universal; however, a direct translation leads to quite a large number of rules. Like for other classes of computationally complete devices, there is a challenge to find a universal system having the smallest number of rules. In this article we present different rule minimization strategies for MPMRS based on encodings and structural transformations. We apply these strategies to the translation of a small universal register machine (Korec (1996) [9]) and we show that there exists a universal MPMRS with 23 rules. Since MPMRS are identical to a restricted variant of P systems with antiport rules, the results we obtained improve previously known results on the number of rules for those systems.

Details DOI

TCS Journal 2011 Journal Article

On generalized communicating P systems with minimal interaction rules

Erzsébet Csuhaj-Varjú
Sergey Verlan

Generalized communicating P systems are purely communicating tissue-like membrane systems with communication rules which allow the movement of only pairs of objects. In this paper, we study the power of these systems in the case of eight restricted variants of communication rules. We show that seven of these restrictions lead to computational completeness, while using the remaining one the systems are able to compute only finite singletons of non-negative integers. The obtained results complete the investigations of the computational power of generalized communicating P systems and provide further examples for simple architectures with simple functioning rules which are as powerful as Turing machines.

Details DOI

TCS Journal 2011 Journal Article

P systems with minimal insertion and deletion

Artiom Alhazov
Alexander Krassovitskiy
Yurii Rogozhin
Sergey Verlan

In this paper, we consider insertion–deletion P systems with priority of deletion over insertion. We show that such systems with one-symbol context-free insertion and deletion rules are able to generate Parikh sets of all recursively enumerable languages ( P s R E ). If a one-symbol one-sided context is added to the insertion or deletion rules, then all recursively enumerable languages can be generated. The same result holds if a deletion of two symbols is permitted. We also show that the priority relation is very important, and in its absence the corresponding class of P systems is strictly included in the family of matrix languages ( M A T ).

Details DOI

TCS Journal 2008 Journal Article

Generalized communicating P systems

Sergey Verlan
Francesco Bernardini
Marian Gheorghe
Maurice Margenstern

This paper considers a generalization of various communication models based on the P system paradigm where two objects synchronously move across components. More precisely, the model uses blocks of four cells such that pairs of objects from two input cells travel together to target output cells. It is shown that the model introduced, based on interactions between blocks, is complete, being able to generate all recursively enumerable sets of natural numbers. It is also proven that completeness is achievable by using a minimal interaction between blocks, i. e. every pair of cells is the input or output for at most one block. It is also shown that the concepts introduced in this paper to define the model may be simulated by more particular communication primitives, including symport, antiport and uniport rules. This enables us to automatically translate a system using interaction rules in any of minimal symport, minimal antiport or conditional uniport P systems.

Details DOI

TCS Journal 2007 Journal Article

On small universal antiport P systems

Erzsébet Csuhaj-Varjú
Maurice Margenstern
György Vaszil
Sergey Verlan

It is known that P systems with antiport rules simulate register machines, i. e. , they are computationally complete. Hence, due to the existence of universal register machines, there exist computationally complete subclasses of antiport P systems with bounded size, i. e. , systems where each size parameter is limited by some constant. However, so far there has been no estimation of these numbers given in the literature. In this article, three universal antiport P systems of bounded size are demonstrated, different from each other in their size parameters. We present universal antiport P systems with 73, 43, and 30 rules where the maximum of the weight of the rules is 4, 5, and 6, respectively.

Details DOI

TCS Journal 2005 Journal Article

A boundary result on enhanced time-varying distributed H systems with parallel computations

Sergey Verlan

Enhanced time-varying distributed H systems (ETVDH systems) are a variant of time-varying distributed H systems (TVDH systems), which is a well-known theoretical model of DNA computing based on splicing. We show that ETVDH systems with 2 components, i. e. , having two sets of rules which act periodically, may generate all recursively enumerable languages by simulating type-0 grammars. We also present a new approach to control the computations that can be used in other models of DNA computing based on splicing.

Details DOI

TCS Journal 2005 Journal Article

Context-free insertion–deletion systems

Maurice Margenstern
Gheorghe Păun
Yurii Rogozhin
Sergey Verlan

We consider a class of insertion–deletion systems which have not been investigated so far, those without any context controlling the insertion–deletion operations. Rather unexpectedly, we found that context-free insertion–deletion systems characterize the recursively enumerable languages. Moreover, this assertion is valid for systems with only one axiom, and also using inserted and deleted strings of a small length. As direct consequences of the main result we found that set-conditional insertion–deletion systems with two axioms generate any recursively enumerable language (this solves an open problem), as well as that membrane systems with one membrane having context-free insertion–deletion rules without conditional use of them generate all recursively enumerable languages (this improves an earlier result). Some open problems are also formulated.

Details DOI