BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Sergey Verlan

Sergey Verlan contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Formal Languages and Automata TheoryComputational ComplexityDiscrete MathematicsComputation and LanguageEmerging TechnologiesDistributed, Parallel, and Cluster ComputingOther Quantitative Biology

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2015arXiv

On insertion-deletion systems over relational words

We introduce a new notion of a relational word as a finite totally ordered set of positions endowed with three binary relations that describe which positions are labeled by equal data, by unequal data and those having an undefined relation between their labels. We define the operations of insertion and deletion on relational words generalizing corresponding operations on strings. We prove that the transitive and reflexive closure of these operations has a decidable membership problem for the case of short insertion-deletion rules (of size two/three and three/two). At the same time, we show that in the general case such systems can produce a coding of any recursively enumerable language leading to undecidabilty of reachability questions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Small Universal Petri Nets with Inhibitor Arcs

We investigate the problem of construction of small-size universal Petri nets with inhibitor arcs. We consider four descriptional complexity parameters: the number of places, transitions, inhibitor arcs, and the maximal degree of a transition, each of which we try to minimize. We give six constructions having the following values of parameters (listed in the above order): $(30,34,13,3)$, $(14, 31, 51, 8)$, $(11, 31, 79, 11)$, $(21,25,13,5)$, $(67, 64, 8, 3)$, $(58, 55, 8, 5)$ that improve the few known results on this topic. Our investigation also highlights several interesting trade-offs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

DNA Circuits Based on Isothermal Constrained Loop Extension DNA Amplification

In this paper, we first describe the isothermal constrained loop extension DNA amplification (ICLEDA), which is a new variant of amplification combining the advantages of rolling circle amplification (RCA) and of strand displacement amplification (SDA). Then, we formalize this process in terms of the theory of formal languages and show, on the basis of this formulation, how to manage OR and AND gates. We then explain how to introduce negation, which allows us to prove that, in principle, it is possible to implement the computation of any boolean function on DNA strands using ICLEDA.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Generalized Communicating P Systems Working in Fair Sequential Model

In this article we consider a new derivation mode for generalized communicating P systems (GCPS) corresponding to the functioning of population protocols (PP) and based on the sequential derivation mode and a fairness condition. We show that PP can be seen as a particular variant of GCPS. We also consider a particular stochastic evolution satisfying the fairness condition and obtain that it corresponds to the run of a Gillespie's SSA. This permits to further describe the dynamics of GCPS by a system of ODEs when the population size goes to the infinity.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Random Context and Semi-Conditional Insertion-Deletion Systems

In this article we introduce the operations of insertion and deletion working in a random-context and semi-conditional manner. We show that the conditional use of rules strictly increase the computational power. In the case of semi-conditional insertion-deletion systems context-free insertion and deletion rules of one symbol are sufficient to get the computational completeness. In the random context case our results expose an asymmetry between the computational power of insertion and deletion rules: systems of size $(2,0,0; 1,1,0)$ are computationally complete, while systems of size $(1,1,0;2,0,0)$ (and more generally of size $(1,1,0;p,1,1)$) are not. This is particularly interesting because other control mechanisms like graph-control or matrix control used together with insertion-deletion systems do not present such asymmetry.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Graph-Controlled Insertion-Deletion Systems

In this article, we consider the operations of insertion and deletion working in a graph-controlled manner. We show that like in the case of context-free productions, the computational power is strictly increased when using a control graph: computational completeness can be obtained by systems with insertion or deletion rules involving at most two symbols in a contextual or in a context-free manner and with the control graph having only four nodes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Matrix Insertion-Deletion Systems

In this article, we consider for the first time the operations of insertion and deletion working in a matrix controlled manner. We show that, similarly as in the case of context-free productions, the computational power is strictly increased when using a matrix control: computational completeness can be obtained by systems with insertion or deletion rules involving at most two symbols in a contextual or in a context-free manner and using only binary matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Minimization Strategies for Maximally Parallel Multiset Rewriting Systems

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 computationally complete; however, a direct translation leads to quite a big 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) 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.

0 citations0 reviewsNo code linkedOpen access