ISSN 2305-9052 · EISSN 2410-7034
Языки: ru · en

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

О НЕСУЩЕСТВОВАНИИ ПРОСТОГО ВАРИАНТА ПОЛИНОМИАЛЬНОГО АЛГОРИТМА ИЗВЛЕЧЕНИЯ КОРНЯ ИЗ ЯЗЫКА (2024)

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

Тип: Статья
Автор (ы): Мельников Борис Феликсович
Ключевые фразы: ФОРМАЛЬНЫЕ ЯЗЫКИ, КОНКАТЕНАЦИЯ ЯЗЫКОВ, СТЕПЕНЬ ЯЗЫКА, КОРЕНЬ ИЗ ЯЗЫКА, ПОЛИНОМИАЛЬНЫЕ АЛГОРИТМЫ

Идентификаторы и классификаторы

УДК
519.1. Комбинаторный анализ. Теория графов
519.713.1. Способы задания и реализации автоматов
519.713.2. Алгебраические вопросы теории автоматов
519.766. Модели языков и языковых структур
eLIBRARY ID
65312691
Текстовый фрагмент статьи