Skip to Main content Skip to Navigation
Journal articles

Single semi-contextual insertion-deletion systems

Abstract : 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.
Complete list of metadata
Contributor : Frédéric Davesne Connect in order to contact the contributor
Submitted on : Sunday, August 1, 2021 - 4:15:00 PM
Last modification on : Thursday, February 10, 2022 - 11:48:03 PM



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



Record views