Cтраница 3
В значительной степени с алгоритмической точки зрения изучаются уравнения в свободной полугруппе, называемые также уравнениями в словах ( см. [41]; [60]; [ 21, § 4; [61], гл. Проблема распознавания разрешимости уравнений в свободной полугруппе разрешима. Лингвистически точнее было бы называть эту проблему проблемой изоморфностщ говорят также проблема изоморфии. Для класса всех полугрупп проблема изоморфизма неразрешима, для коммутативных полугрупп - разрешима ( источники см. в [10], с. [31]
В качестве структуры выступает бесконечное бинарное дерево в графической интерпретации или бесконечная свободная полугруппа Т ( /, г в алгебраической интерпретации. Полугруппой сдвигов служит свободная полугруппа. [32]
Шютценбергером [68] и Л. Н. Шевриным [69] найдены условия, при которых подполугруппа свободной полугруппы является свободной. Подполугруппы свободных полугрупп изучались также Розеном [14] и позднее Коном. [33]
Теория кодовых систем переменной длины, в которой изучаются конечные базисы свободных полугрупп. [34]
Перед тем как перейти к изучению подалгебр свободных алгебр, полезно рассмотреть свободные полугруппы. При изучении свободных полугрупп мы сталкиваемся с теми же проблемами, что и при изучении свободных алгебр, но сами эти проблемы оказываются значительно проще, поскольку мы имеем дело с одной операцией. Сохраняя аналогию с кольцами, мы будем считать, что все рассматриваемые полугруппы обладают единичным элементом, обозначаемым снова через 1; тогда обратимые элементы и атомы определяются так же, как для колец. Особенно важно понять, что является для полугрупп аналогом слабого алгоритма. Как мы видели в § 2.4, слабый алгоритм можно использовать для характеризации свободных алгебр; аналогичный результат будет получен и для полугрупп. [35]
Теорему 6.1 можно использовать для выяснения вопроса, является ли некоторая подполугруппа свободной полугруппы сама свободной. Рассмотрим, например, свободную полугруппу с одним свободным порождающим х ( свободную циклическую полугруппу); ее подполугруппа, порожденная элементами х2 и я3, является коммутативной, и если бы она была свободной, то порождалась бы одним элементом, что, очевидно, не так. С помощью следующей теоремы легко найти другие примеры несвободных подполугрупп свободной полугруппы. [36]
Использовать теорему 6.2. для того чтобы найти алгоритм превращения произвольного конечного подмножества X свободной полугруппы в подмножество X, такое, что ( i) X и X порождают одну и ту же подполугруппу Т, ( ii) если Т - свободная полугруппа, то X - ее множество свободных порождающих. [37]
Если выполняется условие ( П), то для доказательства того, что Т - свободная полугруппа, можно применить теорему 6.1: понятно, что Т не имеет обратимых элементов, отличных от 1; далее, для того чтобы представить некоторый необратимый элемент из Т1 в виде произведения атомов из Г, достаточно записать его в виде произведения наибольшего возможного числа сомножителей, лежащих в Т поскольку S - свободная полугруппа, для данного элемента существует верхняя граница числа этих сомножителей. [38]
Пусть X - насыщенное по входам квазимногообразие автоматов, F F ( X) - свободная полугруппа счетного ранга. Согласно теореме 15.2, слой Хг является F-квазимногообразием. [39]
Предложение 2.4.1. Для любого отображения ср множества А в полугруппу S существует единственный гомоморфизм ф свободной полугруппы А в S, такой, что ф ( х) ( р ( х) для всех х А. [40]
Аналог теоремы 5.11 утверждает существование биекции между псевдомногообразиями конечных полугрупп и потоками рациональных языков из свободных полугрупп. Примером потока языков, для которых различие между синтаксическими моноидами и синтаксическими полугруппами представляет определенный интерес, служит класс локально тестируемых языков ( гл. [41]
В этом вырожденном случае вместо ps можно взять пустое соотношение; обычно и говорят, что свободная полугруппа задается пустым множеством определяющих соотношений. [42]
Это утверждение показывает, что отношение коммутирования является эквивалентностью на множестве всех отличных от 1 элементов свободной полугруппы и что классы эквивалентных элементов, если к ним присоединить 1, являются свободными циклическими полугруппами. [43]
Эта операция ( называемая иногда конкатенацией) ассоциативна, так что Рл становится полугруппой, которая называется свободной полугруппой над алфавитом А. В виде таких произведений, как правило, и записывают элементы свободной полугруппы и называют их словами. Полугруппы Л и В изоморфны тогда и только тогда, когда алфавиты А и В равномощны; мощность алфавита называют рангом соответствующей свободной полугруппы. Отметим, что свободная полугруппа счетного ранга вложима в свободную полугруппу ранга 2, свободная полугруппа данного ранга - в свободную группу того же ранга. Роль свободных полугрупп в общей теории объясняется прежде всего следующим принципиальным фактом: всякая полугруппа является гомоморфным образом подходящей свободной полугруппы. [44]
Эта операция на Л, называемая ино гда конкатенацией, очевидно, ассоциативна, и А называется свободной полугруппой на множестве А. А допускает единственное разложение в произведение элементов из А. [45]