Алгоритмическая проблема

Cтраница 1

Алгоритмическая проблема Пуанкаре может быть сформулирована в чисто алгебраических терминах. Действительно, как доказал Вальдхаузен [96], любые два сплетения Хегора одинакового рода стандартной сферы S3 эквивалентны. [1]

Соответствующая алгоритмическая проблема состоит в вопросе о возможности открытого коллектива алгоритмов, который бы не только перерабатывал операнды, но и видоизменял сам себя. [2]

Типичная массовая алгоритмическая проблема для формальных языков состоит в том, что требуется установить существование алгоритма, который для произвольного языка L, заданного порождающей грамматикой или другой порождающей системой, устанавливает, обладает ли этот язык некоторым свойством. Например, проблема принадлежности связана с проверкой, принадлежит ли произвольное слово а языку L; в проблеме пустоты следует выяснить, пусто ли множество L; в проблеме конечности задача состоит в выяснении, является ли L конечным множеством. [3]

Многие известные алгоритмические проблемы - алгебры и топологии могут быть формулированы как задачи исследования разрешимости определенных классов отношений эквивалентности, и отрицательные решения таких проблем обычно получаются в виде утверждений о наличии неразрешимых отношений среди определенного тина отношений эквивалентности. [4]

Две основные алгоритмические проблемы могут быть определены следующим образом. [5]

Кроме алгоритмических проблем к математической теории грамматик относятся также проблемы оценки сложности вывода в грамматиках. [6]

При обсуждении алгоритмической проблемы распознавания гомотопической сферы было отмечено, что ответ на этот вопрос оказался бы положительным, если бы существовал алгоритм, распознающий тривиальность группы, заданной сбалансированным представлением. [7]

Связь между алгоритмическими проблемами и энтропийными характеристиками групп / / Докл. [8]

Третья часть, Алгоритмические проблемы ( § 14 - 23), является кульминационной. В ней излагается ряд фундаментальных результатов теории, которые, к счастью, поддаются популяризации. Более подробная характеристика содержания книги дана во введении. [9]

ТОЖДЕСТВА ПРОБЛЕМА - алгоритмическая проблема распознавания равенства ( тождества) слов в алгебраич. [10]

Более формальные формулировки этих и других алгоритмических проблем используют теорию нумераций и теорию рекурсивных множеств. Тогда G является факторгруппой свободной группы F ( X) с базой X по нормальной подгруппе N, порожденной множеством R. Для группы G проблема равенства разрешима тогда и только тогда, когда множество a ( N) рекурсивно. [11]

Более формальные формулировки этих и других алгоритмических проблем используют теорию нумераций и теорию рекурсивных множеств. Именно, пусть О ( XRy - конечный код группы. Тогда G является факторгруппой свободной группы F ( X) с базой X по нормальной подгруппе N, порожденной множеством R. Для группы G проблема равенства разрешима тогда и только тогда, когда множество a ( N) рекурсивно. [12]

Подобные вопросы и образуют круг алгоритмических проблем теории грамматик. [13]

Аналогично, положительно была бы решена алгоритмическая проблема сопряженности элементов в нильпотентных группах, если бы в каждой ниль-потентной группе G с конечным числом порождающих для любой пары несопряженных элементов а, Ъ существовал нормальный делитель N конечного индекса такой, что образы а, Ъ в фактор-группе GIN были также несопряженными. [14]

Схема Патерсона всегда останавливается. [15]

Страницы: 1 2 3 4