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

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