Insertion-deletion (or ins-del for short) systems are well studied in formal language theory, especially regarding their computational completeness. The need for many variants on ins-del systems was raised by the computational completeness result of ins-del system with (optimal) size (1, 1, 1; 1, 1, 1). Several regulations like graph-control, matrix and semi-conditional have been imposed on ins-del systems. Typically, computational completeness are obtained as trade-off results, reducing the size, say, to (1, 1, 0, 1, 1, 0) at the expense of increasing other measures of descriptional complexity. In this paper, we study simple semi-conditional ins-del systems, where an ins-del rule can be applied only in the presence or absence of substrings of the derivation string. We show that simple semi-conditional ins-del system, with maximum permitting string length 2 and maximum forbidden string length 1 and sizes (2, 0, 0; 2, 0, 0), (1, 1, 0; 2, 0, 0), or (1, 1, 0; 1, 1, 1), are computationally complete. We also describe RE by a simple semi-conditional ins-del system of size (1, 1, 0; 1, 1, 0) and with maximum permitting and forbidden string lengths 3 and 1, respectively. The obtained results complement the existing results available in the literature. © 2018, Springer International Publishing AG, part of Springer Nature.

Lakshmanan K

Department of Analytics

School of Computer Science and Engineering

Vellore Campus

Fernau H

Kuppusamy L

Raman I.

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

Computational Completeness of Simple Semi-conditional Insertion-Deletion Systems

Unconventional Computation and Natural Computation Lecture Notes in Computer Science

Insertion–deletion (or ins–del for short) systems are simple models of bio-inspired computing. They are well studied in formal language theory, especially regarding their computational completeness. This concerns the question if all recursively enumerable languages can be generated. This ultimately addresses the question if one can build general-purpose computers rooted in this formalism. The descriptional complexity of an ins–del system is typically measured by its size, a 6-dimensional tuple of non-negative integers (e, e′, e′ ′; d, d′, d′ ′) where e is the maximum length of the insertion string, e′ (and e′ ′) is the maximum length of the left (and right) context used for insertion; the last three parameters d, d′, d′ ′ are similarly understood for 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. In this context, the six-tuple explained above is called the ID size of a system. Several regulations like graph-control, matrix and semi-conditional have been imposed on ins–del systems. Typically, the computational completeness results are obtained as trade-offs, reducing the ID size, say, to (1, 1, 0; 1, 1, 0) at the expense of increasing other measures of descriptional complexity. In this paper, we study simple semi-conditional ins–del systems, where an ins–del rule can be applied only in the presence or absence of substrings of the derivation string. This brings along two further natural parameters to measure descriptional complexity, namely, the maximum permitting string length p and the maximum forbidden string length f, usually summarized as the degree d= (p, f). We show that simple semi-conditional ins–del systems of degree (2, 1) and with ID sizes (1 + e, e′, e′ ′; 1 + d, d′, d′ ′) are computationally complete for any e, e′, e′ ′, d, d′, d′ ′∈ { 0 , 1 } , with e+ e′+ e′ ′= 1 and d+ d′+ d′ ′= 1. The obtained results complement and improve on the existing results known from the literature. To prove our results, we also show a new normal form for type-0 grammars that appears to be interesting in its own right. © 2019, Springer Nature B.V.

Natural Computing

Computational completeness of simple semi-conditional insertion–deletion systems of degree (2,1)

A matrix ins-del system is described by a set of insertion-deletion rules presented in matrix form, which demands all rules of a matrix to be applied in the given order. These systems were introduced to model very simplistic fragments of sequential programs based on insertion and deletion as elementary operations as can be found in biocomputing. We are investigating such systems with limited resources as formalized in descriptional complexity. A traditional descriptional complexity measure of such a system is its ins-del size. Summing up the according numbers, we arrive at the sum-norm. We show that matrix ins-del systems with sum-norm 4 and (i) maximum length 3 with only one of insertion or deletion being performed under a one-sided context, or (ii) maximum length 2 with both insertion and deletion being performed under a one-sided context, can describe all recursively enumerable languages. We also show that if a matrix ins-del system of size s can describe the class of linear languages LIN, then without any additional resources, matrix ins-del systems of size s also describe the regular closure of LIN. © 2019, Springer Nature Switzerland AG.

SOFSEM 2019: Theory and Practice of Computer Science Lecture Notes in Computer Science

On Matrix Ins-Del Systems of Small Sum-Norm

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.

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

A regulated extension of an insertion-deletion system known as graph-controlled insertion-deletion (GCID) system has several components and each component contains some insertion-deletion rules. A rule is applied to a string in a component and the resultant string is moved to the target component specified in the rule. When resources are so limited (especially, when deletion is context-free) then GCID systems are not known to describe the class of recursively enumerable languages. Hence, it becomes interesting to find the descriptional complexity of such GCID systems of small sizes with respect to language classes below RE. To this end, we consider closure classes of linear languages. We show that whenever GCID systems describe LIN with t components, we can extend this to GCID systems with just one more component to describe, for instance, 2-LIN and with further addition of one more component, we can extend to GCID systems that describe the rational closure of LIN. © IFIP International Federation for Information Processing 2017.

Fulltext

Descriptional Complexity of Formal Systems Lecture Notes in Computer Science

Graph-Controlled Insertion-Deletion Systems Generating Language Classes Beyond Linearity

Acta Informatica

On path-controlled insertion–deletion systems

RAIRO - Theoretical Informatics and Applications

On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems

Fundamenta Informaticae

Random Context and Semi-conditional Insertion-deletion Systems

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