О длине минимальной алфавитной склейки для класса линейных регулярных языков

В кандидатской диссертации [1] была поставлена и решена задача о нахождении верхней оценки на минимальную длину слов из регулярного языка, склеивающихся (то есть имеющих совпадающий образ) при алфавитном кодировании (если такая склейка вообще существует). В данной статье исследуется задача о нахождении соответствующих нижних оценок на длину склейки для случая, когда регулярные языки имеют линейную функцию роста, а схема кодирования преобразует все буквы входного алфавита в один и тот же символ. Для такого кодирования образ слова однозначно определяется по его длине. Приводятся нижние оценки, совпадающие по порядку с верхними оценками из [1] для таких языков и такого кодирования. Кроме того, для этого подслучая приводится более точная верхняя оценка.