In this paper, we introduce some basic measures for insertion-deletion system and matrix insertion-deletion system. These measures are based on the number of variables, the number of productions and the number of symbols in a grammar. We show that with respect to these measures, both the systems are more succinct over context-free grammars in representing certain families of context-free languages.

Lakshmanan K

Department of Analytics

School of Computer Science and Engineering

Vellore Campus

Kamala Krithivasan

Raman I

Krithivasan K.

Vellore Institute of Technology (VIT) is a private university located in&nbsp;Tamil Nadu, India. Founded in 1984, as Vellore Engineering College, the institution offers 20 undergraduate, 34 postgraduate, four integrated and four research programs. It has campuses in Vellore, Amravati, Bhopal and Chennai.

VIT is one of the top ranked private universities in India according to NIRF, THE and QS Rankings.&nbsp;Govt. of India has recognized&nbsp;VIT, Vellore as an&nbsp;Institution of Eminence. This has allowed VIT to take independent quality initiatives and move up in world ranking.

&nbsp;

&nbsp;

VIT University

On Succinct Description of Certain Context-Free Languages by Ins-Del and Matrix Ins-Del Systems

International Journal of Foundations of Computer Science

Matrix insertion-deletion systems combine the idea of matrix control (a control mechanism well established in regulated rewriting) with that of insertion and deletion (as opposed to replacements). Given a matrix insertion-deletion system, the size of such a system is given by a septuple of integers (k; n, i′, i′ ′; m, j′, j′ ′). The first integer k denotes the maximum number of rules in (length of) any matrix. The next three parameters n, i′, i′ ′ denote the maximal length of the insertion string, the maximal length of the left context, and the maximal length of the right context of insertion rules, respectively. The last three parameters m, j′, j′ ′ are similarly understood for deletion rules. In this paper, we improve on and complement previous computational completeness results for such systems, showing that matrix insertion-deletion systems of size (1) (3; 1, 0, 1; 1, 0, 1), (3; 1, 0, 1; 1, 1, 0), (3; 1, 1, 1; 1, 0, 0) and (3; 1, 0, 0; 1, 1, 1) (2) (2; 1, 0, 1; 2, 0, 0), (2; 2, 0, 0; 1, 0, 1), (2; 1, 1, 1; 1, 1, 0) and (2; 1, 1, 0; 1, 1, 1), are computationally complete. Further, we also discuss linear and metalinear languages and we show how to simulate grammars characterizing them by matrix insertion-deletion systems of size (3; 1, 1, 0; 1, 0, 0), (3; 1, 0, 1; 1, 0, 0), (2; 2, 1, 0; 1, 0, 0) and (2; 2, 0, 1; 1, 0, 0). We also generate non-semilinear languages using matrices of length three with context-free insertion and deletion rules. © 2017, Springer Science+Business Media B.V., part of Springer Nature.

Natural Computing

Investigations on the power of matrix insertion-deletion systems with small sizes

Matrix insertion-deletion systems combine the idea of matrix control (as established in regulated rewriting) with that of insertion and deletion (as opposed to replacements). We improve on and complement previous computational completeness results for such systems, showing (for instance) that matrix insertion-deletion systems with matrices of length two, insertion rules of type (1, 1, 1) and context-free deletions are computationally complete. We also show how to simulate (Kleene stars of) metalinear languages with several types of systems with very limited resources. We also generate non-semilinear languages using matrices of length three with context-free insertion and deletion rules. © Springer International Publishing Switzerland 2016.

Unconventional Computation and Natural Computation Lecture Notes in Computer Science

Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion

Grammar Systems:

Past Present

Theoretical Computer Science

Matrix insertion–deletion systems

P systems with minimal insertion and deletion

Proceedings of the 1st International Workshop on AI Methods for Interdisciplinary Research in Language and Biology

On Representing Natural Languages and Bio-molecular Structures using Matrix Insertion-deletion Systems and its Computational Completeness

On succinct description of certain context-free languages by ins-del and matrix ins-del systems

Journal	International Journal of Foundations of Computer Science
Publisher	World Scientific Publishing Co. Pte Ltd
ISSN	01290541
Open Access	No