|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
О длине минимальной алфавитной склейки для класса линейных регулярных языковстатья
- Авторы: Дергач П.С., Раджабов Ж.И.
- Журнал: Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460)
- Том: 21
- Номер: 3
- Год издания: 2017
- Издательство: [б.и.]
- Местоположение издательства: М.
- Первая страница: 120
- Последняя страница: 130
- Аннотация: В кандидатской диссертации первого автора публикации была поставлена и решена задача о нахождении верхней оценки на минимальную длину слов из регулярного языка, склеивающихся (то есть имеющих совпадающий образ) при алфавитном кодировании. В статье ставится вопрос о нахождении соответствующих нижних оценок. Рассмотрен случай, когда регулярные языки имеют линейную функцию роста, а схема кодирования преобразует все буквы входного алфавита в один и тот же символ. Для такого кодирования образ слова однозначно определяется по его длине. Приводятся нижние оценки, совпадающие по порядку с верхними оценками из кандидатской диссертации для таких языков и такого кодирования. Кроме того, для этого подслучая удается уменьшить соответствующую верхнюю оценку. Все результаты являются новыми и аккуратно формально доказанными.
- Добавил в систему: Дергач Пётр Сергеевич