Separating words by occurrences of subwords |
| |
| Authors: | M N Vyalyi R A Gimadeev |
| |
| Institution: | 1. Dorodnitsyn Computing Center, ul. Vavilova 40, Moscow, 119333, Russia
2. Moscow Institute of Physics and Technology, Institutskii per. 9, Dolgoprudnyi, 141700, Russia
|
| |
| Abstract: | We obtain some lower bounds for the complexity of word separation by occurrences of subwords. In the case of length 1 subwords, we show that the bound is exact up to a constant factor. Connection with the problem of separating words by automata is considered. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
