About the checking the uniqueness of the alphabetical decoding problem in the class of regular languages with polynomial growth function

P. S. Dergach

Lomonosov Moscow State University

Abstract: The article consists of two parts. In the first part we observe the problem of checking the uniqueness of the alphabetical decoding in the class of regular languages. We present a series of several restrictions on these languages, the full fillment of which allows you to build a new solution algorithm and greatly improve its complexity compared to the complexity of the same algorithm in [4]. The second part of the article is devoted to the issue of proof of the uniqueness of the alphabetical decoding for the class of regular languages with polynomial growth. The results obtained in the first part of the article form the basis of an algorithm that solves the problem under consideration. We introduce the new technique that allows to implement for languages with a polynomial growth the assumptions that are listed in the first part of the article.

Keywords: regular languages, polynomial growth function, alphabetical decoding.