Cтраница 3
Если детерминированная функция / определена на множестве А всех сверхслов в алфавите Л, то в силу условий 1) и 2) она однозначно распространяется на множество А, для произвольного слова а длины I значение / ( а) совпадает с началом длины I значения / ( а ( 5), где р - произвольное сверхслово в алфавите А. [31]
Предложение 1.8. а) Пусть W - сверхслово. Тогда среди правых сверхслову все подслова которых содержатся в W, есть как максимальное, так и минимальное. [32]
F, в к-ром а - произвольное сверхслово. В этом случае значение функции ф ( s, а) определяется как множество всех тех и только тех состояний, к-рые встречаются в последовательности f ( s, а) бесконечное число раз. [33]
Определение 1.4. Сверхсловом называется слово, бесконечное в обоих направлениях. Слово, бесконечное только влево, называется левым сверхсловом, а бесконечное вправо - правым сверхсловом. [34]
Большинство комбинаторных результатов данной части основывается на рассмотрении бесконечных слов или сверхслов. В данном пункте собраны основные технические факты и конструкции, относящиеся к сверхсловам в алгебрах. [35]
В - множество всех выходных символов, бесконечное число раз встречающихся в сверхслове Р, то скажем, что автомат 3tg реагирует на входное сверхслово а00 посредством подмножества В выходных символбв. [36]
Определение 1.4. Сверхсловом называется слово, бесконечное в обоих направлениях. Слово, бесконечное только влево, называется левым сверхсловом, а бесконечное вправо - правым сверхсловом. [37]
В - множество всех выходных символов, бесконечное число раз встречающихся в сверхслове Р, то скажем, что автомат 3tg реагирует на входное сверхслово а00 посредством подмножества В выходных символбв. [38]
Образ множества конечных слов плотен в пространстве сверхслов. Эквивалентным словам соответствуют одинаковые сверхслова. Отношению соответствует отношение - на сверхсловах. Образ множества конечных слов плотен в пространстве сверхслов. [39]
Для этого нам достаточно построить семейство vi слов в А таких, что VQ v, Vi i - ViCiVidiViCiVi. Поскольку У очевидным образом имеет бесконечно много вхождений в VQQ, то и тоже имеет бесконечно много вхождений в VQQ. Таким образом, сверхслово VQQ первично. [40]
Основой структурных рассуждений служит рассмотрение полупростой ( полупервичной) части и сведение к ней путем факторизации по радикалу. Оказывается, первичной является моно-миальная алгебра, соответствующая периодическому слову. Она порождает матричное многообразие Var ( Mn), где п - длина периода. Если в слове есть периодический кусок сверхслова и00 периода, большего п, и выполняется тождество /, которого нет в ( n x п) - матрицах, то с помощью этого тождества период можно испортить. При этом можно получить слово, лексикографически меньшее и. Далее работает техника выделенных наборов слов, позволяющая сделать рассуждения в полупростой части конструктивными. Набор слов называется выделенным, если факторалгебра по идеалу, порожденному этим набором, ниль-потентна. Свойство выделенности набора слов или сверхслов не зависит от радикала. Наконец, перекачка - это свойство, очень похожее на алгебраичность. Унитарной замкнутости многообразия, порожденного алгеброй матриц, отвечает лемма о вычеркиваниях и приписках. Рассмотрение неприводимых модулей соответствует рассмотрению сверхслова, линейно не пред-ставимого меньшими. Покажем на примере, как это работает. [41]
Основой структурных рассуждений служит рассмотрение полупростой ( полупервичной) части и сведение к ней путем факторизации по радикалу. Оказывается, первичной является моно-миальная алгебра, соответствующая периодическому слову. Она порождает матричное многообразие Var ( Mn), где п - длина периода. Если в слове есть периодический кусок сверхслова и00 периода, большего п, и выполняется тождество /, которого нет в ( n x п) - матрицах, то с помощью этого тождества период можно испортить. При этом можно получить слово, лексикографически меньшее и. Далее работает техника выделенных наборов слов, позволяющая сделать рассуждения в полупростой части конструктивными. Набор слов называется выделенным, если факторалгебра по идеалу, порожденному этим набором, ниль-потентна. Свойство выделенности набора слов или сверхслов не зависит от радикала. Наконец, перекачка - это свойство, очень похожее на алгебраичность. Унитарной замкнутости многообразия, порожденного алгеброй матриц, отвечает лемма о вычеркиваниях и приписках. Рассмотрение неприводимых модулей соответствует рассмотрению сверхслова, линейно не пред-ставимого меньшими. Покажем на примере, как это работает. [42]