Lakshmanan K.: Descriptional Complexity of Matrix and Graph-Controlled Insertion-Deletion Systems

The seminar is organized by the Formal Model Research Group at the Department of Information Systems, Faculty of Information Technology, Brno University of Technology. As its central scientific topic, it discusses formal models and their applications. Recent presentations are to be found at http://www.fit.vutbr.cz/~meduna/work/doku.php?id=talks:seminar.

Author: prof. Lakshmanan Kuppusamy, School of Computer Science & Engineering, Department of Computational BioSciences, VIT University, India
Title: Descriptional Complexity of Matrix and Graph-Controlled Insertion-Deletion Systems
Abstract: Lila Kari introduced the Insertion-deletion system (abbreviated as ins-del system) in formal language theory. Informally, the insertion and deletion operations are defined as follows: if a string w is inserted between two parts u and v of a string uv to get uwv, then we call the operation insertion, whereas if a substring x is deleted from a string uxv to get uv, then we call the operation deletion. Suffixes of u and prefixes of v are called left and right context, respectively. An ins-del system is well described by its size, denoted by (n, i, i; m, j, j) where the parameters from left to right denote (i) the maximal length of the insertion string, (ii) the maximal length of the left context in insertion rules, (iii) the maximal length of the right context used in insertion rules, (iv)-(vi) denote the similar things in deletion rules.

Computational completeness for ins-del systems can even be achieved with rule size (1,1,1; 1,1,1) but with no rule size strictly smaller than this. This fact has motivated to study ins-del systems in combination with regulation mechanisms and to achieve the computational completeness with smaller/trade-off size than (1,1,1; 1,1,1). Some of the important variants of ins-del systems are graph-controlled ins-del (GCID) systems, matrix ins-del (MID) system. In matrix ins-del system, the rules are in the form of a matrix and a matrix is a set of ins-del rules. During the derivation, if a matrix is chosen, then all the rules of the matrix are applied in sequentially and in order to the derived string. In graph-controlled ins-del system, there are several components and each component has a set of rules. A transition is performed on the string based on any applicable rule in the current component and the resultant string is moved to the target component specified in the rule itself.

In this talk, we see some computational completeness results of matrix and graph-controlled ins-del systems, reducing the ID size, say, to (1,1,0,1,1,0) at the expense of increasing other measures of descriptional complexity. If time permits, we will also see representation of linear languages using these systems with their descriptional complexity measure sizes.