Cтраница 2
Это следует из теоремы Тице, поскольку добавление образующих или следствий определяющих соотношений ровно, как и обратные операции, сохраняют разрешимость проблемы слов. [16]
Разложение разрывной планарной группы в свободное произведение с объединенными подгруппами открывает, очевидно, возможности для изучения алгебраических свойств G алгебраическими методами и решения с применением 2.2.9 и 2.2.11 проблемы слов и проблемы сопряженности. [17]
Проблема слов представляет собой далеко идущее обобщение поисков Тезея, Если поиски Тезея могут происходить в произвольном, но к о н е ч н о м лабиринте, то проблема слов является в определенном смысле проблемой поиска в бесконечном лабиринте. [18]
Коммутант может быть использован для исследования геометрических свойств узла, особенно, если он конечно порожден ( см. [ 42, гл. Используя решение проблемы слов для свободных произведений с объединенными подгруппами и элементарную теорию групп, получим первую часть следующего утверждения. [19]
Для тех, кто немного знаком с теорией групп. Покажите, что для любой конечно-определенной группы проблема слов частично разрешима. [20]
Мы не будем здесь пытаться объяснять доказательство этого результата, скажем только, что оно использует нечто вроде диагонального метода, употребляемого для доказательства несчетности множества действительных чисел. Классической и наиболее важной проблемой разрешения для группового представления является проблема слов ( см. 1.1.9): существует ли алгоритм для определения по произвольному слову над множеством порождающих данного представления, является ли оно следствием определяющих соотношений, представления и, тем самым, определяет ли оно единичный элемент. Ответ на этот вопрос может быть и отрицательным, то есть существуют представления, проблема слов для которых алгоритмически неразрешима, более того, возможно выписать пример такого представления за сравнительно короткое время. [21]
Теория групп и современная алгебра вообще изобилует интересными разрешимыми и неразрешимыми проблемами. При этом многие из них касаются свойств слов и образующих, сходных с проблемой слов. [22]
Однако позднее выяснилось, что подобные явления имеют место и для некоторых, казалось бы, более узких проблем, возникающих в самых разнообразных разделах математики. В первую очередь здесь следует указать на ряд алгебраических проблем, приводящих к различным вариантам проблемы слов, которые исследовались советскими математиками. [23]
Опираясь на строгое понятие нормального алгорифма, данное в разд. Именно, скажем, что проблема равенства слов для моноида М, заданного копредставлением Л; , разрешима, если существует такой алгорифм 5t над алфавитом Ли. В противном случае проблема слов называется неразрешимой. [24]
Итак, слова ас и ассс неэквивалентны. Приведенное в примере 4 подробное решение проблемы слов для конкретного ассоциативного исчисления во многом характеризует понятия и методы, возникающие и при исследовании проблемы слов для других исчислений. Нам остается еще пояснить содержательный смысл проблемы слов и ее значение в современной алгебре. Это удобно сделать не конкретном примере. [25]
Большой класс комбинаторных задач, связанных со случайными процессами, рассмотрен в монографии Такача [38], первое-издание которой вышло в 1967 г. Отметим работу Рота [77], посвященную теории флюктуации сумм независимых случайных величин. В ней предлагается метод проверки тождеств, используемых в комбинаторике теории флюктуации, путем перевода их в легко проверяемые тождества для классических симметрических функций. Осуществив алгебраизацию вероятностной задачи, Рота свел ее к проблеме слов для бакстеровых алгебр. [26]
Мы не будем здесь пытаться объяснять доказательство этого результата, скажем только, что оно использует нечто вроде диагонального метода, употребляемого для доказательства несчетности множества действительных чисел. Классической и наиболее важной проблемой разрешения для группового представления является проблема слов ( см. 1.1.9): существует ли алгоритм для определения по произвольному слову над множеством порождающих данного представления, является ли оно следствием определяющих соотношений, представления и, тем самым, определяет ли оно единичный элемент. Ответ на этот вопрос может быть и отрицательным, то есть существуют представления, проблема слов для которых алгоритмически неразрешима, более того, возможно выписать пример такого представления за сравнительно короткое время. [27]
Итак, слова ас и ассс неэквивалентны. Приведенное в примере 4 подробное решение проблемы слов для конкретного ассоциативного исчисления во многом характеризует понятия и методы, возникающие и при исследовании проблемы слов для других исчислений. Нам остается еще пояснить содержательный смысл проблемы слов и ее значение в современной алгебре. Это удобно сделать не конкретном примере. [28]
Имелось много конкретных примеров алгоритмов, которые понимались как процедуры, для выполнения которых при любых входных данных требуется конечное число шагов. Решение Дэна проблемы слов для группы поверхности рода, большего 1 ( см. 4.1.1), дает другой пример такого рода. [29]
Итак, слова ас и ассс неэквивалентны. Приведенное в примере 4 подробное решение проблемы слов для конкретного ассоциативного исчисления во многом характеризует понятия и методы, возникающие и при исследовании проблемы слов для других исчислений. Нам остается еще пояснить содержательный смысл проблемы слов и ее значение в современной алгебре. Это удобно сделать не конкретном примере. [30]