О несуществовании простого варианта полиномиального алгоритма извлечения корня из языка
Автор: Мельников Б.Ф.
Статья в выпуске: 1 т.13, 2024 года.
Бесплатный доступ
Для стандартной операции конкатенации слов, рассматриваемой как умножение, естественным образом определяется конкатенация языков, а на основе последней операции - степень языка и, при наличии, корень заданной степени. При описании алгоритмов построения языка, являющегося корнем степени M из заданного языка, большое значение имеют так называемые потенциальные корни: это такие слова (не языки), рассматриваемая M-я степень которых входит в заданный язык. Несложно показать, что все потенциальные корни для заданного языка строятся с помощью полиномиального алгоритма. Эта задача, по-видимому, не упрощается при рассмотрении слов и языков над 1-буквенным алфавитом - что и делается в настоящей статье. Табуированная пара потенциальных корней - это такая пара, конкатенация слов которой в язык не входит. В предыдущих публикациях на тему описания алгоритмов извлечения корней из языка возникала гипотеза, что полиномиальный алгоритм извлечения корня из языка может быть описан на основе рассмотрения только множества табуированных пар - путем перебора специально описываемых подмножеств множества потенциальных корней. В настоящей статье показывается, что подобный алгоритм (называемый «простым») невозможен, т.е. если и существует полиномиальный алгоритм извлечения корня из языка, то он (алгоритм) должен использовать некоторую дополнительную информацию.
Формальные языки, конкатенация языков, степень языка, корень из языка, полиномиальные алгоритмы
Короткий адрес: https://sciup.org/147243207
IDR: 147243207 | DOI: 10.14529/cmse240103
Список литературы О несуществовании простого варианта полиномиального алгоритма извлечения корня из языка
- Мельников Б.Ф., Мельникова A.A. О задачах извлечения корня из заданного конечного языка // International Journal of Open Information Technologies. 2023. Vol. 11, no. 5. P. 1-14.
- 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.
- Мельников Б.Ф. Полиномиальный алгоритм построения оптимального инверсного морфизма // International Journal of Open Information Technologies. 2023. Vol. 11, no. 6. P. 1-10.
- 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.
- Мельников Б.Ф. Полурешетки подмножеств потенциальных корней в задачах теории формальных языков. Часть I. Извлечение корня из языка // International Journal of Open Information Technologies. 2022. Vol. 10, no. 4. P. 1-9.
- Рябов Г.Г. О четверичном кодировании кубических структур // Вычислительные методы и программирование. 2009. Т. 10, № 3. С. 340-347.
- Рябов Г.Г. Хаусдорфова метрика на гранях N-мерного куба // Фундаментальная и прикладная математика. 2010. Т. 16, № 1. С. 151-155.
- Рябов Г.Г. Полиморфизм символьных троичных матриц и генетическое пространство кратчайших K-путей в N-кубе // International Journal of Open Information Technologies. 2015. Vol. 3, no. 7. P. 1-11.
