We study matrix insertion grammars (MIS) towards representation of recursively enumerable languages with small size. We show that pure MIS of size (3; 1, 2, 2) (i.e., having ternary matrices inserting one symbol in two symbol context) 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 language or an intersection with a regular language followed by a weak coding. The obtained results complete known results on insertiondeletion systems from DNA computing area. © Springer International Publishing AG 2017.

Lakshmanan K

Department of Analytics

School of Computer Science and Engineering

Vellore Campus

Fernau H

Verlan S.

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

Universal Matrix Insertion Grammars with Small Size

Unconventional Computation and Natural Computation Lecture Notes in Computer Science

AbstractInsertion and deletion are operations that occur commonly in DNA processing and RNA editing. Since biological macromolecules can be viewed as symbols, gene sequences can be represented as strings and structures can be interpreted as languages. This suggests that the bio-molecular structures that occur at different levels can be theoretically studied by formal languages. In the literature, there is no unique grammar formalism that captures various bio-molecular structures. To overcome this deficiency, in this paper, we introduce a simple grammar model called the matrix insertion–deletion system, and using it we model several bio-molecular structures that occur at the intramolecular, intermolecular and RNA secondary levels.

Fulltext

International Journal of Applied Mathematics and Computer Science

Modelling DNA and RNA secondary structures using matrix insertion–deletion systems

We consider graph-controlled insertion-deletion systems and prove that the systems with sizes (i) (3; 1, 1, 1; 1, 0, 1), (ii) (3; 1, 1, 1; 1, 1, 0) and (iii) (2; 2, 0, 0; 1, 1, 1) are computationally complete. Moreover, graph-controlled insertion-deletion systems simulate linear languages with sizes (2; 2, 0, 1, 1, 0, 0), (2; 2, 1, 0; 1, 0, 0), (3; 1, 0, 1; 1, 0, 0), or (3; 1, 1, 0; 1, 0, 0). Simulations of metalinear languages are also studied. The parameters in the size (k; n, i’, i’'; m, j’, j’') of a graph-controlled insertion-deletion system denote (from left to right) the maximum number of components, the maximal length of the insertion string, the maximal length of the left context for insertion, the maximal length of the right context for insertion; a similar list of three parameters concerning deletion follows. © IFIP International Federation for Information Processing 2016.

Descriptional Complexity of Formal Systems Lecture Notes in Computer Science

Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems

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.

Journal	Data powered by TypesetUnconventional Computation and Natural Computation Lecture Notes in Computer Science
Publisher	Data powered by TypesetSpringer International Publishing
ISSN	0302-9743
Open Access	0