О несуществовании простого варианта полиномиального алгоритма извлечения корня из языка

Борис Феликсович Мельников

Аннотация


Для стандартной операции конкатенации слов, рассматриваемой как умножение, естественным образом определяется конкатенация языков, а на основе последней операции – степень языка и, при наличии, корень заданной степени. При описании алгоритмов построения языка, являющегося корнем степени M из заданного языка, большое значение имеют так называемые потенциальные корни: это такие слова (не языки), рассматриваемая M-я степень которых входит в заданный язык. Несложно показать, что все потенциальные корни для заданного языка строятся с помощью полиномиального алгоритма. Эта задача, по-видимому, не упрощается при рассмотрении слов и языков над 1-буквенным алфавитом — что и делается в настоящей статье. Табуированная пара потенциальных корней — это такая пара, конкатенация слов которой в язык не входит. В предыдущих публикациях на тему описания алгоритмов извлечения корней из языка возникала гипотеза, что полиномиальный алгоритм извлечения корня из языка может быть описан на основе рассмотрения только множества табуированных пар — путем перебора специально описываемых подмножеств множества потенциальных корней. В настоящей статье показывается, что подобный алгоритм (называемый «простым») невозможен, т.е. если и существует полиномиальный алгоритм извлечения корня из языка, то он (алгоритм) должен использовать некоторую дополнительную информацию.

Ключевые слова


формальные языки; конкатенация языков; степень языка; корень из языка; полиномиальные алгоритмы.

Полный текст:

PDF

Литература


Melnikov B.F., Melnikova А.А. On the problems of extracting the root from a given finite language. International Journal of Open Information Technologies. 2023. Vol. 11, no. 5. P. 1–14. (in Russian)

Melnikov B.F., Korabelshchikova S.Yu., Dolgov V.N. On the task of extracting the root from the language. International Journal of Open Information Technologies. 2019. Vol. 7, no. 3. P. 1–6.

Melnikov B.F. A polynomial algorithm for constructing the optimal inverse morphism. International Journal of Open Information Technologies. 2023. Vol. 11, no. 6. P. 1–10. (in Russian)

Stockmeyer L.J. The polynomial-time hierarchy. Theoretical Computer Science. 1976. Vol. 3, no. 1. P. 1–22.

Chandra A.K., Kozen D., Stockmeyer L.J. Alternation. Journal of the ACM. 1981. Vol. 28, no. 1. P. 114–133.

Immerman N. TDescriptive Complexity. Berlin: Springer, 1999. 284 p.

Hromkovic J. Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Berlin: Springer, 2003. 323 p.

Hromkovic J. Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Berlin: Springer, 2004. 547 p.

Melnikov B.F. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part I. Extracting the root from the language. International Journal of Open Information Technologies. 2022. Vol. 10, no. 4. P. 1–9. (in Russian)

Ryabov G.G. On the quaternary coding of cubic structures. Computational methods and programming. 2009. Vol. 10, no. 3. P. 340–347. (in Russian)

Ryabov G.G. Hausdorff metric on the faces of an N-dimensional cube. Fundamental and Applied Mathematics. 2010. Vol. 16, no. 1. P. 151–155. (in Russian)

Ryabov G.G. Polymorphism of symbolic ternary matrices and genetic space of shortest K-paths in an N-cube. International Journal of Open Information Technologies. 2015. Vol. 3, no. 7. P. 1–11. (in Russian)




DOI: http://dx.doi.org/10.14529/cmse240103