Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion
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 suc
- PDF / 302,313 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 78 Downloads / 167 Views
Fachbereich 4 – Abteilung Informatikwissenschaften, Universit¨ at Trier, 54286 Trier, Germany [email protected] 2 School of Computing Science and Engineering, VIT University, Vellore 632 014, India [email protected] 3 School of Information Technology and Engineering, VIT University, Vellore 632 014, India [email protected]
Abstract. 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.
Keywords: Matrix ins-del systems Metalinear languages
1
·
Computational completeness
·
Introduction
It is assumed that inserting or deleting words in between parts of sentences often take place when processing natural languages. This concept also frequently occurs in DNA processing and RNA editing; see [2,3,26]. Based on the insertion operation, Marcus introduced external contextual grammars [19] as an attempt to mathematically model natural language phenomena. A different variety of linguistically motivated contextual grammars are the semi-contextual grammars studied by Galiukschov [10], which can be viewed as insertion grammars. The deletion operation as a basis of a grammatical derivation process was introduced in [14]. Insertion and deletion together were first studied in [15] and the corresponding grammatical mechanism is called insertion-deletion system (abbreviated as ins-del system). Informally, if a string η is inserted between two parts w1 and w2 of a string w1 w2 to get w1 ηw2 , we call the operation insertion, whereas c Springer International Publishing Switzerland 2016 M. Amos and A. Condon (Eds.): UCNC 2016, LNCS 9726, pp. 35–48, 2016. DOI: 10.1007/978-3-319-41312-9 4
36
H. Fernau et al.
if a substring δ is deleted from a string w1 δw2 to get w1 w2 , we call the operation deletion. Suffixes of w1 and prefixes of w2 are called contexts. Several variants of ins-del systems have been considered in literature and among them the important variants (from our perspective) are ins-del P systems [1], context-free ins-del systems [20], graph-controlled ins-del systems [7,8,13], matrix insertion systems [18], matrix ins-del systems [16,25], etc. We refer to the survey article [28] for more details of variants of ins-del systems. In a matrix ins-del system, the insertion-deletion rules are given in matrix form. If a matrix l is chosen for derivation, then all the rules in the matrix l are applied in order and no rule of the matrix is exempted. In a size (k; n, i , i ; m, j , j
Data Loading...
