Seminar dedicat lui Iurie Rogojin

On the 11th of November 2016 in 14:00 Institute of Mathematics and Computer Science organizes in Chisinau a workshop "Unconventional Computing Systems" in commemoration of Yuri Rogozhin (room 340).

1. Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems
Artiom Alhazov, Omar Belingheri, Rudolf Freund, Sergiu Ivanov, Antonio E. Porreca, and Claudio Zandron


In this paper we consider P systems working with multisets with integer multiplicities. We focus on a model in which rule applicability is not influenced by the contents of the membrane. We show that this variant is closely related to blind register machines and integer vector addition systems. Furthermore, we describe the computational power of these models in terms of linear and semilinear sets of integer vectors.

2. NetControl4BioMed - Automatic discovery of combined drug therapy
Vladimir Rogojin


Recent results in network science have demonstrated that network control theory can lead to the development of novel therapeutic approaches for systemic diseases like cancer through the computational analysis of the structure of intracellular molecular interaction networks. These networks are a formal representation of relations between numerous components within cells that are used as a mean for formal holistic reasoning about biological structures. In particular, network controllability studies focus on discovering combinations of external interventions that can drive the biological system to a desired configuration. In practice, these studies can be translated into finding a combined multi-drug therapy in order to achieve a desired response from a cell. We develop a pipeline that finds a minimal set of nodes controlling a given set of targets within a network. The pipeline highlights those control nodes for which there are known FDA approved drugs. The network is generated automatically through querying of a number of pathway databases. The pipeline is deployed as an online web-service.

3. How graphs help us fight cancer: structural control of disease networks
Eugen Czeizler


Computational analysis of the structure of intra-cellular molecular interaction networks can suggest novel therapeutic approaches for systemic diseases like cancer. Recent research in the area of network science has shown that network control theory can be a powerful tool in the understanding and manipulation of such bio-medical networks. In 2011, Liu et al. developed a polynomial time optimization algorithm for computing the size of the minimal set of nodes controlling a given linear network. In 2014, Gao et al. generalized the problem for target structural control, where the objective is to optimize the size of the minimal set of nodes controlling a given target within a linear network. The working hypotheses in this case is that partial control might be "cheaper" (in the size of the controlling set) than the full control of a network. The authors developed a greedy algorithm searching for the minimal solution of the structural target control problem, however, no suggestions were given over the actual complexity of the optimization problem. We prove that the structural target controllability problem is NP-hard when looking to minimize the number of driven nodes within the network, i.e., the first set of nodes which need to be directly controlled in order to structurally control the target. We also show that the greedy algorithm provided by Gao et al. in 2014 might in some special cases fail to provide a valid solution, and a subsequent validation step is required. Also, we improve their search algorithm using several heuristics, obtaining in the end up to a 10-fold decrease in running time and also a significant decrease of the size of the minimal solution found by the algorithms. Finally, we demonstrate the applicability of the target network control approach by applying it in the analysis of three types of cancers: breast, pancreatic and ovarian. We build in each case a signaling transduction protein-protein interaction network and focus on the so-called "essential proteins" specific to each cancer type in our study. We show that the cancer essential proteins are efficiently controllable from a (relatively small) computable set of driver nodes. Moreover, we adjust the method to find the driver nodes among FDA-approved drug-target nodes. Interestingly, we find that while many of the drugs acting on our driver nodes are part of known cancer therapies, some of them are not used for the cancer types analyzed here; also some drug-target driver nodes identified by our algorithms are not known to be used in any cancer therapy. Overall we show that a better understanding of the control dynamics of illnesses through mathematical modelling could pave the way for new efficient therapeutic approaches and personalized medicine.

4. Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States
Serghei Verlan, Sergiu Ivanov


In this presentation, we consider leftist insertion-deletion systems (LIDS), in which all rules have contexts on the same (left) side, and may only insert or delete one symbol at a time. We start by introducing extended rules, in which the contexts may be specified as regular expressions, instead of fixed words. We prove that in this case the computational completeness is achieved when additional control mechanisms are used (graph control with two states, matrix control with binary matrices and random-context control). We then show how rules with regular contexts can be simulated by conventional rules of sizes $(1,1,0; 1,2,0)$ or $(1,2,0; 1,1,0)$. However, this simulation does not hold in the controlled case, in general. Hence, we provide a construction simulating an arbitrary 2-tag system using extended rules and which can be rewritten in terms of conventional rules of sizes above, which implies that the latter systems are universal.

5. Small Asynchronous P Systems with Inhibitors Defining Non-semilinear Sets
Artiom Alhazov


The objective of this work is to present concrete membrane systems generating non-semilinear sets that are small in the following way: Attention is paid to such parameters of descriptional complexity as the alphabet size, the number of rules, the total number of inhibitors used, and the maximal rule size. A total of 54 systems is described, depending on the exact requirements; the presented systems for the same requirements are incomparable.

6. Logic in Computer Science, Engineering and Industry
Yuri Gurevich, Microsoft Research


In software industry, engineers do formal logic day in and day out, even though they may not realize that. As a rule, they have not studied logic. Instead, they spent a lot of time studying calculus which they use rarely, if ever. I'll try to illustrate why logic is so relevant and why it is hard for software engineers to pick it up.

7. Variants of Energy-Controlled P Systems
Artiom Alhazov, Rudolf Freund, Sergiu Ivanov


We consider several variants of P systems where the computations are controlled by the energy consumed by the productions and show some computational completeness results.