Header menu link for other important links
X
On the Power of Generalized Forbidding Insertion-Deletion Systems
H. Fernau, , I. Raman
Published in Springer Science and Business Media Deutschland GmbH
2020
Volume: 12442 LNCS
   
Pages: 52 - 63
Abstract
We consider generalized forbidding insertion-deletion systems (GFID) where each insertion-deletion rule is associated with a set of words and the rule can be applied to a string only if every word of is not a subword of the string. The parameters in the size of a GFID system denote (from left to right) the maximum length of a word in the maximal length of an insertion string, the maximal length of the left context for insertion, the maximal length of the right context for insertion; the last three parameters follow a similar pattern with respect to deletion. We show that GFID systems of sizes where with describe all recursively enumerable languages, by explaining algorithms that transform a given type-0 grammar in some normal form to a GFID system of the required size. © 2020, Springer Nature Switzerland AG.