On the properties of languages that are stable to the drop/paste operations

P. S. Dergach^a, V. B. Kudryavtsev<sup>b

a</sup> Lomonosov Moscow State University
^b Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: The article is devoted to the drop and paste operations, which have been promoted by V.I. Levenshtein. Closure operators are introduced for these operations. For the paste operator the existence, finiteness and uniqueness of the basis in closed classes are proved, and for the drop operator, non-existence for the in finite class and existence, finiteness and uniqueness for the finite are proved. The automata complexity of closed classes is investigated. The problems of completeness, precompleteness, expressibility are solved.

Keywords: drop and paste operations, closed class, regular language, basis, automata complexity, problems of completeness/precompleteness/expressibility.