|
Intelligent systems. Theory and applications, 2018, Volume 22, Issue 4, Pages 153–167
(Mi ista166)
|
|
|
|
On the properties of languages that are stable to the drop/paste operations
P. S. Dergacha, V. B. Kudryavtsevb a 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.
Citation:
P. S. Dergach, V. B. Kudryavtsev, “On the properties of languages that are stable to the drop/paste operations”, Intelligent systems. Theory and applications, 22:4 (2018), 153–167
Linking options:
https://www.mathnet.ru/eng/ista166 https://www.mathnet.ru/eng/ista/v22/i4/p153
|
Statistics & downloads: |
Abstract page: | 183 | Full-text PDF : | 71 | References: | 32 |
|