Дискретно-непрерывная математика (стр. 89 )

Микромодуль 9.

Идивидуальные тестовые задачи

1. Пусть J — нулевой F класс полугруппы S. Докажите, что NJ(S) содер­жит нетривиальный комбинаторный идеал.

2. Пусть J — регулярный F класс полугруппы S.

а) Определим на S отношение эквивалентности ≡ следующим образом:

Докажите, что ≡ есть отношение конгруэнтности.

б) Пусть φ — гомоморфизм, ассоциированный с ≡, и J ' =φ(J) — F класс в φ (S). Докажите, что

3. Пусть J — регулярный F класс полугруппы S. Докажите, что

Микромодуль 10.

Методы вычисления сложности конечных полугрупп

Цель настоящего микромодуля состоит в том, чтобы разработать методы вычисления (групповой) сложности заданной конечной полугруппы или заданного приведенного конечного автомата М. В основном пред­ставленные здесь результаты доказаны только для тех автоматов, по­лугруппы которых представляют собой объединение групп. Однако мно­гие методы, видимо, можно распространить на произвольные конеч­ные полугруппы.

Приводится набор аксиом и доказывается, что им может удовлет­ворять только одна функция. Показывается, что функция #G, рассматриваемая для полугрупп, являющихся объединением групп, удовлетворяет этим аксиомам. Используются аксиомы для развития нескольких подходов к вычислению #G.

1. Аксиомы

1.1. Обозначения. Предполагается, что все рассматриваемые полу­группы имеют конечный порядок. Символ Т ≤ S указывает, что Т есть подполугруппа полугруппы S, в частности S ≤ S. Символ N обозна­чает множество неотрицательных целых чисел, а L есть непустая совокупность конечных полугрупп, причем образы гомоморфизмов полу­групп из S снова принадлежат P, т. е. если SL и S →→ Т,

то TL.

Заметим, что если полугруппы S и S1 — изоморфны, то SL тогда и только тогда, когда Далее {0}L , так как для любой

полугруппы S существует гомоморфизм S→→{0} и по предположению P — непустое множество. Наконец, если то Sj P для j = 1, ..., п.

Примерами совокупностей полугрупп, удовлетворяющих сформу­лированным требованиям, служат все конечные полугруппы, все регу­лярные конечные полугруппы, все конечные полугруппы, представ­ляющие собой объединение групп, и все абелевы конечные полугруппы.

1.2. Определение (P аксиомы для сложности). Пусть P — свой­ство полугрупп и L —совокупность полугрупп, замкнутая относительно взятия образов гомоморфизмов полугрупп из L. В этом случае отображение θ: L → N называется G сложностью для L относительно P, если θ удовлетворяет следую­щим трем аксиомам.

Аксиома 1. Пусть Тогда

Аксиома 2. (Основная лемма для сложности). Пусть I — комбина­торный идеал полугруппы S.

Тогда,

Аксиома 3. Пусть S ≠ {0} есть GM полугруппа. Тогда

1.3. Предложение. Пусть L и P — такие, как в определении 1.2. Тогда существует самое большее одно отображение, являющееся G слож­ностью для L относительно P.

Доказательство. Предположим, что θ 1 и θ 2 — два отображения, яв­ляющиеся G сложностью для L относительно P. Пусть S — полугруп­па в L наименьшего порядка, такая, что

По аксиоме 2 S≠{0}. Но тогда по лемме 2.19 из микромодуля 9 или

1) S имеет UMPE, или 2) где для k = 1, ..., п. Случай 3 невозможен, так как по аксиоме 1

и, учитывая то, как была выбрана полугруппа S, θ1(Si) = θ2 (Si) для i = 1, ..., п. Следовательно, S имеет UMPE и тогда по лемме 2.19 из микромодуля 9 или S есть GM полугруппа, или S содержит ненулевой комби­наторный идеал I. Последнее невозможно, так как по аксиоме 2 θj (S) = θj (S/I) для j = 1, 2 и θ1 (S/I) = θ2 (S/I) по определению полугруппы S.

Следовательно, S будет GМ полугруппой. Отметим, что |RLM(S)|<| S|, когда S есть GM полугруппа. Следовательно,

и тогда по аксиоме 3 в обоих случаях получаем, что Это противоречие. Таким образом, предложение дока­зано.

2. Теорема

Единственность функции, могущей быть G сложностью, установлен на в предыдущем пункте. Теперь рассмотрим вопросы, свя­занные с существованием сложности. Основная теорема этого пункта характеризует различными способами G сложность для L относительно P, где L есть совокупность всех полугрупп, представляю­щих собой объединение групп, и P есть совокупность всех GM полу­групп.

Начнем с небольшого обзора теории полугрупп, являющихся объединением групп. Предполагается, что все рассматриваемые в этом параграфе полугруппы представляют собой объединения групп. Оп­ределение и некоторые результаты можно найти в определении 15 и в предложении 1 из микромодуля 7.

2.1. Краткое изложение результатов п. 3.8 микромодуля 9 для полу­групп, являющихся объединением групп.

а) α = α' для и все они сохраняются при огра-

ничениях.

в) Предложение 3.17 из микромодуля 9 справедливо для . (важный результат).

г) есть комбинаторная полугруппа, так как F есть отношение конгруэнтности, когда S представляет собой объединение групп.

2.2. Определение. Говорят, что последовательность S1 →→S2→→S3 →→ ... отображается на последовательность Т1→→ Т2 →→T3 →→ ..., если для всех i = 1,2,3, ... существуют эпиморфизмы Si →→ Ti.

2.3. Замечание. Пусть α и β — два оператора на полугруппе S, такие,

что (например,

и т. п.). Рассмотрим последовательность с чередованием α и β для S,

Если некоторый эпиморфизм в последовательности не будет соб­ственным (эпиморфизм собственный, если он не взаимно однозначный), то с этого места последовательность становится постоянной. Предпо­ложим, например, что

Тогда

и т. д.

Теперь введем несколько функций, определенных на совокупности полугрупп, являющихся объединением групп. Эти функции принимают целые значения. Основная теорема этого пункта доказывает, что все функции равны между собой.

2.4. Определение. Пусть где — совокупность полугрупп,

представляющих собой объединение групп.

а) Рассмотрим где G сложность полугруппы S.

б) Рассмотрим последовательность

(б)