ВЕСТНИК ЮЖНО-УРАЛЬСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА. СЕРИЯ: ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА И ИНФОРМАТИКА

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

Основной предмет статьи - рассмотрение задач, возникающих при исследовании необходимых условий равенства бесконечных итераций конечных языков. В предыдущих публикациях автором рассматривались примеры применения соответствующего этому равенству специального бинарного отношения эквивалентности на множестве конечных языков, причем рассматривались как примеры, описывающие необходимые условия его выполнения, так и примеры его использования. К одному из таких необходимых условий применены два варианта сведeния рассматриваемой задачи: к конечным автоматам и к бесконечным итерационным деревьям. Также в статье приведены несколько вариантов важной гипотезы, формулируемой для множества конечных языков; ее исследование дает и иные варианты сведeния рассматриваемой задачи к специальным задачам для недетерминированных конечных автоматов. При этом в случае выполнения сформулированной гипотезы некоторые из таких задач решаются за полиномиальное время, а некоторые не решаются; при продолжении работ по данной тематике последний факт может дать возможность переформулировки проблемы P = NP в виде специальной задачи теории формальных языков.