Cтраница 3
В основе конструкции Новикова лежит результат Тьюринга о неразрешимости проблемы равенства для полугрупп с сокращением. Конструкция примера в дальнейшем была значительно упрощена - группы Буна ( Boone W. W. / / Ann. [31]
В основе конструкции Новикова лежит результат Тьюринга о неразрешимости проблемы равенства для полугрупп с сокращением. Конструкция примера в дальнейшем была значительно упрощена - группы Буна ( Воопе W. W. / / Ann. [32]
Как показано Магнусом [1932], группы с одним определяющим соотношением имеют разрешимую проблему равенства. [33]
Платон мог бы выразиться примерно в том же духе, если бы проблема равенства его вообще хоть сколько-нибудь волновала. Но во всем диалоге Государство слово равенство ( в социальном смысле) не встречается ни разу. [34]
Многообразие V ( r лиево нильпотентных алгебр индекса г является конечно аппроксимируемым, поэтому проблема равенства разрешима в нем. Однако мы хотим показать, что эта проблема разрешима с помощью алгоритма, использующего понятие базиса Гребнера. [35]
Любая полициклическая группа является ФА -, ФАВ -, ФАС-группой, а потому в ней разрешимы проблемы равенства, вхождения и сопряженности. [36]
Действительно, факторгруппы п ( Т) / Но и п ( Т) / Н изоморфны свободным группам, а следовательно, проблема равенства слов в них разрешима. [37]
Наш набросок ( который более или менее следует книге А. И. Мальцева 11965 ]), конечно, не является кратчайшим путем к доказательству неразрешимости проблемы равенства, но зато он одновременно вводит ряд стандартных систем для порождения классов языков. Простейшие из этих систем ( конечные автоматы, контекстно-свободные грамматики) будут детально изучены в следующих главах. [38]
Для любого и е а, Ь, с, d в &2 выполняется fueatn зз feam, a для любого специального слова uew соотношение fuewm fs feam выполняется в 972 тогда и только тогда, когда uew иеа в марковской системе о - Согласно предложению 5.2.1, проблема равенства слову feam в 2 неразрешима. [39]
Проблема равенства и неравенства возникла с делением общества на классы. [40]
Теперь мы обсудим некоторые простейшие алгоритмические вопросы, связанные с определенными выше группами. Проблема равенства слов [81], [82] для групп п ( Т) в ориентируемом случае положительно решена была Дэном, который придумал для этой цели алгоритм, носящий теперь его имя. [41]
В моноиде, заданном копр ед став ленив м, соотношение z rn ss fz2tn выполняется тогда и только тогда, когда z z2 в системе Маркова &0. Следовательно, проблема равенства для копредставления & неразрешима. [42]
Опираясь на строгое понятие нормального алгорифма, данное в разд. Именно, скажем, что проблема равенства слов для моноида М, заданного копредставлением Л; , разрешима, если существует такой алгорифм 5t над алфавитом Ли. В противном случае проблема слов называется неразрешимой. [43]
В работе [50] выяснена тесная связь между классическими алгоритмическими проблемами и понятием аппроксимируемости алгебры относительно соответствующих предикатов. После этого уже довольно просто решаются проблемы равенства и вхождения для нильпотентных групп, а также некоторые другие алгоритмические вопросы. Надо заметить, что развитие и применение идей, содержащихся в [50], и в настоящее время еще далеки от своего исчерпания. [44]
Даже для полугрупп с одним определяющим соотношением до сих пор ( 1977) не найден алгоритм, решающий проблему тождества в общем случае. Для групп с одним определяющим соотношением алгоритм, решающий проблему равенства, был построен давно [13]; но уже для двух соотношений вопрос остается открытым. Доказана разрешимость проблемы равенства слов для коммутативных полугрупп. Для коммутативных групп разрешима также и проблема изоморфизма. [45]