Single semi-contextual insertion-deletion systems - Université d'Évry Access content directly
Journal Articles Natural Computing Year : 2021

Single semi-contextual insertion-deletion systems


In this paper we consider the model of single insertion-deletion systems that at each step insert or delete a single symbol in a context-free manner (i.e. at any position in the word). The corresponding operation is performed if the word contains a set of permitting (that have to be present in the word) and/or forbidding (that must not be present in the word) strings of some size. The main result of this paper states that if forbidding strings of size 2 and permitting strings of size 1 are used then computational completeness can be achieved; moreover, checking for a single permitting symbol is sufficient. We also show that in the case of systems having rules with forbidding conditions only, all regular languages can be obtained. Finally, we show the computational non-completeness in the case of systems using rules with forbidding strings of size 1 (single symbols) and permitting strings of any finite size.
Not file

Dates and versions

hal-03311601 , version 1 (01-08-2021)



Sergiu Ivanov, Sergey Verlan. Single semi-contextual insertion-deletion systems. Natural Computing, 2021, 20, pp.703-712. ⟨10.1007/s11047-021-09861-3⟩. ⟨hal-03311601⟩
75 View
0 Download



Gmail Facebook Twitter LinkedIn More