Скінченні підгрупи і спряженість у групах скінченних автоматів

Размещено на http://www.allbest.ru/

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ІМЕНІ ТАРАСА ШЕВЧЕНКА

АВТОРЕФЕРАТ

СКІНЧЕННІ ПІДГРУПИ І СПРЯЖЕНІСТЬ У ГРУПАХ СКІНЧЕННИХ АВТОМАТІВ

Дисертацією є рукопис.

Робота виконана у Київському національному університеті імені Тараса Шевченка.

Науковий керівник:

кандидат фіз.-мат. наук, ОЛІЙНИК Андрій Степанович, Київський національний університет імені Тараса Шевченка, доцент кафедри алгебри та математичної логіки.

Офіційні опоненти:

доктор фізико-математичних наук, професор, АРТЕМОВИЧ Орест Дем'янович, Прикарпатський національний університет імені Василя Стефаника, професор кафедри алгебри і геометрії; кандидат фізико-математичних наук, ЛЕЩЕНКО Юрій Юрійович, Черкаський національний університет імені Богдана Хмельницького, доцент кафедри алгебри і математичного аналізу.

З дисертацією можна ознайомитись в науковій бібліотеці ім. М. Максимовича Київського національного університету імені Тараса Шевченка (м. Київ, вул. Володимирська, 58).

Автореферат розісланий «12» травня 2011 р.

Вчений секретар спеціалізованої вченої ради Журавльов В. М.

Загальна характеристика роботи

Актуальність теми. Розвиток теорії груп і, зокрема, таких її розділів, як комбінаторна та геометрична теорія груп, значною мірою був простимульований проблемою, яку сформулював В. Бернсайд Burnside, W. On an unsettled question in the theory of discontinuous groups / W. Burnside // Quart. J. Pure Appl. Math. -- 1902. -- no. 33. -- Pp. 230-238. у 1902 році про те, чи зобов'язана скінченно породжена група, кожен елемент якої має скінченний порядок, бути скінченною. Ця проблема, яку пізніше стали називати загальною проблемою Бернсайда, підштовхнула дослідників до конструювання і вивчення груп, які описуються засобами різноманітних розділів математики, володіють набором несподіваних властивостей і тісно пов'язуються з, на перший погляд, далекими один від одного об'єктами. Негативне розв'язання загальної проблеми Бернсайда стало причиною поглиблення досліджень груп автоморфізмів нескінченних кореневих дерев.

Теорія груп автоморфізмів нескінченних локально скінченних кореневих дерев є важливим напрямком досліджень сучасної геометричної теорії груп. Особливого значення такі групи набули після того, як С. В. Альошину Алёшин, С. В. Конечные автоматы и проблема Бернсайда о периодических группах / С. В. Алёшин // Мат. заметки. -- 1972. -- Т. 11, N 3. -- С. 319-328., В. І. Сущанському Сущанский, В. И. Периодические -группы подстановок и неограниченная проблема Бернсайда / В. И. Сущанский // ДАН СССР. -- 1979. -- Т. 247, N 3. -- С. 557-562., Р. І. Григорчуку Григорчук, Р. И. К проблеме Бернсайда о периодических группах / Р. И. Григорчук // Функц. анализ и его прил. -- 1980. -- Т. 14, N 1. -- С. 53-54. Григорчук, Р. И. Степени роста конечно-порожденных групп и теория инвариантных средних / Р. И. Григорчук // Изв. АН СССР. Сер. матем. -- 1984. -- Т. 48, N 5. -- С. 939-985., С. Сідкі та Н. Гупті Gupta, N. On the Burnside problem for periodic groups / N. Gupta, S. Sidki // Math. Z. -- 1983. -- Vol. 182, no. 3. -- Pp. 385-388. вдалося знайти приклади нескінченних скінченно породжених періодичних груп, які точно діють на кореневих деревах. Тим самим було одержано негативний розв'язок загальної проблеми Бернсайда. Елементи таких груп, а також самі групи можна задавати за допомогою автоматів-трансляторів Глушков, В. М. Абстрактная теория автоматов / В. М. Глушков // Успехи матем. наук. -- 1961. -- Т. 16, N 5. -- С. 3-62., зокрема скінченних. Можна досліджувати інші класи груп, які визначаються автоматами вказаного типу. Це приводить до появи нових цікавих класів груп, які діють автоморфізмами на регулярних кореневих деревах, зокрема гіллястих та самоподібних груп (Р. І. Григочук Grigorchuk, R. I. Just infinite branch groups / R. I. Grigorchuk // New horizons in pro- groups / Ed. by M. P. F. du Sautoy, D. Segal, A. Shalev. -- Birkhдuser Verlag, Basel, 2000. -- Vol. 184 of Progress in Mathematics. -- Pp. 121-179., В. В. Некрашевич Nekrashevych, V. Self-similar groups / V. Nekrashevych. -- American Mathematical Society, Providence, RI, 2005. -- Vol. 117 of Mathematical Surveys and Monographs. -- xi+231 pp., Л. Бартольді Bartholdi, L. From fractal groups to fractal sets / L. Bartholdi, R. Grigorchuk, V. Nekrashevych // Fractals in Graz 2001. -- Trends Math. -- Birkhдuser, Basel, 2003. -- Pp. 25-118.) та виникнення природних алгоритмічних питань про такі групи. А саме, питань пов'язаних зі скінченністю чи нескінченністю груп автоматів, їх періодичністю, ростом груп автоматів, описом динамічних характеристик дії груп цих автоматів на кореневому дереві. Загальною характеристикою цих проблем є знаходження зв'язку між властивостями автомата, що визначає групу, та властивостями самої цієї групи чи її природної дії на дереві.

Особливе значення серед груп автоморфізмів кореневих дерев посідає група всіх скінченно станових автоморфізмів регулярного кореневого дерева. Проте для неї залишаються відкритими такі природні питання як опис її групи автоморфізмів, знаходження класів спряжених елементів, розв'язання проблеми спряженості. Дослідженню питань, пов'язаних зі скінченністю тих підгруп групи скінченно станових автоморфізмів, які породжені скінченними автоматами-трансляторами, та умовам спряженості елементів цієї групи, присвячено дану роботу, тема якої, з огляду на сказане вище, є актуальною.

Зв'язок роботи з науковими програмами, планами, темами. Тема дисертаційної роботи пов'язана з науковими дослідженнями кафедри алгебри та математичної логіки Київського національного університету імені Тараса Шевченка, які ведуться за науково дослідною темою “Розробка алгебраїчних та геометричних методів дослідження алгебраїчних структур з використанням комбінаторних та категорних підходів” (номер державної реєстрації 0106U005862).

Мета і задачі дослідження. Встановити необхідні та достатні умови скінченності груп скінченних автоматів. Дослідити автомати без циклів з виходом та описати групи автоматів без циклів з виходом з невеликою кількістю станів. Дослідити проблему спряженості в групі всіх скінченно станових автоморфізмів регулярного кореневого дерева.

Методи дослідження. У дисертаційній роботі використовуються методи геометричної та комбінаторної теорії груп і теорії груп автоморфізмів кореневих дерев.

Наукова новизна одержаних результатів. У дисертаційній роботі одержано такі нові результати:

*введено поняття автомата без циклів з виходом та доведено, що група автомата без циклів з виходом є скінченною;

*для певних автоматів без циклів з виходом з станами доведено точність дії їх груп на -ому рівні відповідного кореневого дерева;

*знайдено точну оцінку порядку групи автомата без циклів з виходом над бінарним алфавітом як функцію кількості станів автомата;

*доведено критерій нескінченності абелевих груп автоматів над бінарним алфавітом;

*з точністю до ізоморфізму знайдено повний список груп автоматів без циклів з виходом над бінарним алфавітом з 2, 3, 4 та 5 станами;

*доведено критерій спряженості елементів скінченного порядку в групі всіх скінченно станових автоморфізмів регулярного кореневого дерева;

*доведено критерій спряженості з додавальною машиною в групі всіх скінченно станових автоморфізмів бінарного кореневого дерева.

Практичне значення одержаних результатів. Результати роботи мають теоретичне спрямування і можуть бути використані при дослідженні груп автоморфізмів кореневих дерев, самоподібних груп, вивченні класів спряженості, зазначених класів груп.

Особистий внесок здобувача. Основні результати отримані автором самостійно.

Апробація результатів дисертації. Результати дисертації доповідалися і обговорювалися на семінарі “Теорія груп та напівгруп” при механіко-математичному факультеті Київського національного університету імені Тараса Шевченка, на алгебраїчному семінарі Київського національного університету імені Тараса Шевченка, а також на конференціях:

*VI Міжнародній алгебраїчній конференції в Україні (м. Кам'янець-Подільський, 2007 р.);

*VII Міжнародній алгебраїчній конференції в Україні (м. Харків, 2009 р.);

*Українському математичному конгресі - 2009 (м. Київ, 2009 р.);

*Humboldt Cosmos: Science and Society (м. Київ, 2009 р.);

Публікації. Основні положення дисертаційного дослідження викладено у чотирьох наукових статтях [1, 2, 3, 4] опублікованих в журналах, що входять до переліку наукових фахових видань ВАК України, та у чотирьох тезах доповідей на міжнародних наукових конференціях [5, 6, 7, 8].

Структура і об'єм роботи. Дисертаційна робота складається зі вступу, чотирьох розділів та списку використаних джерел. Повний обсяг дисертації складає 114 сторінок друкованого тексту. Список використаних джерел обсягом 6 сторінок містить 44 найменування.

Основний зміст роботи

У першому розділі наводяться означення та огляд необхідних результатів, які використовуються в наступних розділах дисертаційної роботи. Результати цього розділу є загальновідомими.

Другий розділ дисертаційної роботи присвячено умовам скінченності груп автоматів та властивостям дій таких груп на кореневих деревах.

В підрозділі 2.1 вводиться поняття автомата без циклів з виходом, яке спирається на наступні означення.

Означення 14. Циклом в автоматі називається послідовність попарно різних станів , , для яких існує послідовність літер така, що для та . При цьому число називається довжиною циклу.

Означення 15. Цикл в автоматі називається циклом з виходом, якщо існує , , та такі, що . В іншому випадку кажуть, що цей цикл є циклом без виходу.

Автоматом без циклів з виходом називається такий автомат, що не містить циклів з виходом. автомат геометричний комбінаторний спряженість

Для класу автоматів без циклів з виходом доведена

Теорема 2.4. Група, породжена скінченним автоматом без циклів з виходом, є скінченною.

Ця теорема дає достатню умову скінченності групи автомата, яка в загальному випадку не є необхідною. Відповідні приклади вказано в роботі.

Наступна теорема встановлює ще одну достатню умову скінченності групи автомата.

Теорема 2.7. Нехай -- мінімізований автомат над алфавітом такий, що . Тоді група скінченна.

В підрозділі 2.2 наводяться достатні умови нескінченності групи автомата.

Розглянемо підмножини

множини станів автомата.

Для перевірки нескінченності групи автомата, може бути використаний

Наслідок 2.13. Якщо

то автомат породжує нескінченну групу.

Наступна достатня умова узагальнює запропоновані раніше On classification of groups generated by 3-state automata over a 2-letter alphabet / I. Bondarenko, R. Grigorchuk, R. Kravchenko et al. // Algebra and Discrete Mathematics. -- 2008. -- no. 1. -- Pp. 1-163. -- arXiv:0803.3555v1. способи перевірки нескінченності групи автомата.

За автоматом над бінарним алфавітом будується відображення на множині всіх підмножин множини станів . Для покладемо , якщо містить парну кількість активних станів, і інакше, де множина визначається правилом

Наступні теореми встановлюють критерій існування сферично транзитивного автоморфізму в групі .

Теорема 2.15. Якщо відображення має цикл, відмінний від , то група , породжена автоматом , містить сферично транзитивний автоморфізм, а тому є нескінченною.

Теорема 2.16. Нехай група, породжена автоматом , містить сферично транзитивний автоморфізм. Тоді відображення має цикл, відмінний від циклу .

Оскільки сферично транзитивний автоморфізм має нескінченний порядок, то теорема 2.15 дає достатню умову нескінченності групи автомата.

В підрозділі 2.3 встановлюється наступний результат, який за певних додаткових умов дозволяє будувати групи підстановок на множині , ізоморфні групі автомата без циклів з виходом.

Теорема 2.18. Нехай автомат без циклів з виходом, в кожному стані якого реалізується підстановка з деякої фіксованої абелевої підгрупи групи , містить станів. Якщо елементи діють однаково на всіх словах довжини , то .

З цієї теореми легко одержати оцінку порядку групи автомата без циклів з виходом як функцію від кількості станів автомата.

Наслідок 2.19. Нехай автомат без циклів з виходом, в кожному стані якого реалізується підстановка з деякої фіксованої абелевої підгрупи групи , містить станів. Тоді для порядку групи , породженої автоматом , має місце оцінка

Для випадку бінарного алфавіту в підрозділі 2.4 встановлюється точна оцінка порядку групи автомата без циклів з виходом.

Теорема 2.24. Нехай -- автомат без циклів з виходом над бінарним алфавітом та . Тоді для порядку групи , породженої автоматом , має місце оцінка

В підрозділі 2.5 досліджуються абелеві групи автоматів над бінарним алфавітом.

Якщо для кожного стану автомата визначити автоморфізм

то критерій абелевості групи автомата може бути сформульований наступним чином.

Теорема 2.25. Автомат породжує абелеву групу тоді і лише тоді, коли для всіх таких, що має місце рівність та для всіх таких, що виконується рівність .

Цей факт обґрунтовує коректність

Означення 17. Для автомата , що породжує абелеву групу, визначимо зсув рівністю

де стан такий, що ; якщо для всіх станів виконується умова , то покладемо .

В абелевому випадку має місце твердження, обернене до теореми 2.4, що встановлює

Теорема 2.26. Нехай мінімізований автомат , , породжує абелеву групу. Тоді наступні умови еквівалентні:

1. ;

2. має цикл з виходом;

3. група нескінченна;

4. група нетривіальна без скруту.

Таким чином, абелева група автомата є скінченною тоді і лише тоді, коли автомат не містить циклів з виходом.

Третій розділ присвячено дослідженню автоматів без циклів з виходом над бінарним алфавітом з невеликою кількістю станів.

В підрозділі 3.1 наведено конструктивні доведення наступних теорем.

Теорема 3.1. Нехай є групою, породженою (скінченним, без циклів з виходом) автоматом над алфавітом , та для кожного стану підстановка належить групі . Тоді група також є групою, породженою (скінченним, без циклів з виходом) автоматом над алфавітом .

Теорема 3.2. Нехай є групою, породженою (скінченним, без циклів з виходом) автоматом над алфавітом . Тоді група для кожного натурального також є групою, породженою (скінченним, без циклів з виходом) автоматом над алфавітом .

Використовуючи конструкції з їх доведень, можна побудувати автомати, які породжують вінцевий добуток та прямий степінь за автоматом, що породжує початкову групу.

Зокрема, одержуємо такі твердження.

Наслідок 3.3. Нехай група породжується (скінченним, без циклів з виходом) автоматом над бінарним алфавітом. Тоді групи та породжуються (скінченним, без циклів з виходом) автоматом над бінарним алфавітом.

Наслідок 3.4. Нехай , натуральні числа. Існує автомат без циклів з виходом з станами над -елементним алфавітом, який породжує групу .

В підрозділі 3.2 наводяться серії автоматів без циклів з виходом та встановлюється, які групи вони породжують.

А саме, доводяться наступні твердження.

Твердження 3.5. Для кожного існує автомат без циклів з виходом над бінарним алфавітом з станами, група якого ізоморфна групі .

Твердження 3.6. Існує автомат без циклів з виходом над бінарним алфавітом з 4 станами, група якого ізоморфна групі .

Твердження 3.7. Для кожного існує автомат без циклів з виходом над бінарним алфавітом з станами, група якого ізоморфна групі .

Твердження 3.8. Для кожного існує автомат без циклів з виходом над бінарним алфавітом з станом, група якого ізоморфна групі , , .

При обчисленні груп автоматів без циклів з виходом над бінарним алфавітом з 5 станами були виявлені приклади, які зручно записувати, використовуючи наступне означення.

Означення 18. Підвінцевим добутком групи підстановок з групою за нормальною підгрупою називається напівпрямий добуток з природною дією на , де підгрупа складається лише з тих елементів , які задовольняють умову для будь-яких .

Для позначення підвінцевого добутку групи з групою за нормальною підгрупою використовується запис .

Твердження 3.9. Існує автомат без циклів з виходом над бінарним алфавітом з 5 станами, група якого ізоморфна групі

де .

Твердження 3.10. Існує автомат без циклів з виходом над бінарним алфавітом з 5 станами, група якого ізоморфна групі

де .

Доведення цих тверджень є конструктивними. Необхідні автомати вказуються явно.

Ці приклади разом з результатами попереднього підрозділу покривають всі групи автоматів без циклів з виходом над бінарним алфавітом з 4 станами, які були спочатку одержані за допомогою комп'ютера.

Підрозділ 3.3 містить результати комп'ютерних обчислень груп автоматів без циклів з виходом над бінарним алфавітом. Обчислення виконувались за допомогою програмного пакету GAP та з використанням теореми 2.18.

Автомати, всім станам яких відповідає одна і та ж підстановка, були виключені з розгляду. При цьому для автоматів з двома станами були одержані групи:

*, ;

з трьома -- групи:

*, ;

*, ;

з чотирьма -- групи:

*, ;

*, ;

*, ;

*, .

Список груп

*, ,

*, ,

*, ,

*, ,

*, ,

*, ,

*, ,

*, ,

*, ,

*, ,

*, ,

*, ,

*, ,

де

містить повний перелік груп автоматів без циклів з виходом над бінарним алфавітом з 5 станами.

Четвертий розділ присвячено дослідженню проблеми спряженості в групі скінченно станових автоморфізмів .

Класи спряженості цієї групи не можна одержати, як перетин з нею класів спряженості Gawron, P. W. Conjugation in tree automorphism groups / P. W. Gawron, V. V. Nekrashevych, V. I. Sushchansky // Internat. J. Algebra Comput. -- 2001. -- Vol. 11, no. 5. -- Pp. 529-547. групи всіх автоморфізмів . Існують приклади елементів Григорчук, Р. И. Автоматы, динамические системы и группы / Р. И. Григорчук, В. В. Некрашевич, В. И. Сущанский // Тр. Мат. ин-та им. В. А. Стеклова. -- 2000. -- Т. 231. -- С. 134-214. спряжених в групі , але не спряжених в групі .

Для елементів скінченного порядку в підрозділі 4.1 встановлено наступний критерій спряженості.

Теорема 4.6. Нехай і два скінченно станові автоморфізми скінченного порядку, що спряжені в групі . Тоді і спряжені в групі .

Для підстановки на множині та літери позначимо через довжину циклу, якому належить , в циклічному розкладі . Для автоморфізму множину всіх літер, що належать циклам довжини 1 підстановки позначимо через , тобто

В підрозділі 4.2 розглядається питання спряженості в групі всіх скінченно станових автоморфізмів.

Зв'язок між спряженістю елементів в групі та спряженістю станів їх першого рівня і степенів самих елементів встановлює

Теорема 4.10. Нехай , підстановки і спряжені в групі , існує бієктивне відображення , для кожного автоморфізми і спряжені в групі та для кожного з множини автоморфізми і спряжені в групі . Тоді і спряжені в групі .

Якщо підстановки і складаються з одного циклу, то теорема 4.10 може бути сформульована в більш компактному вигляді.

Теорема 4.11. Нехай . Припустимо, що підстановки і з групи є циклами довжини та і спряжені в групі . Тоді і спряжені в групі .

В підрозділі 4.3 досліджується спряженість зі спеціальним автоморфізмом -- додавальною машиною над бінарним алфавітом.

Для автоморфізму визначимо множину автоморфізмів

де слово довжини складене лише з нулів.

Наступна теорема встановлює критерій спряженості з додавальною машиною над бінарним алфавітом.

Теорема 4.13. Нехай та спряжені в групі . Автоморфізми та спряжені в групі тоді і лише тоді, коли множина скінченна.

На практиці для використання наведеного критерію спряженості з додавальною машиною може бути корисне

Твердження 4.14. Нехай скінченно становий автоморфізм. Множина скінченна тоді і лише тоді, коли множина скінченна.

Наводяться приклади використання цих тверджень як для доведення спряженості так і для перевірки не спряженості елементів нескінченного порядку в групі .

Висновки

В дисертації досліджуються деякі питання для групи всіх скінченно станових автоморфізмів регулярного кореневого дерева. А саме, встановлюються умови скінченності та нескінченності самоподібних підгруп цієї групи (вони можуть бути задані скінченними автоматами) та умови спряженості елементів в цій групі.

Серед груп скінченних автоматів виділено спеціальний клас автоматів без циклів з виходом. В діаграмі Мура таких автоматів не існує ребер, які би виводили з циклів, тобто автомат після переходу в стан, що належить деякому циклу, не може вийти з цього циклу.

Для автоматів без циклів з виходом встановлено, що вони породжують скінченні групи. За додаткової умови, що група автомата має бути абелевою, виявилось, що лише автомати без циклів з виходом породжують скінченні групи. Доведено, що група автомата без циклів з виходом, в кожному з станів якого реалізується підстановка з деякої фіксованої абелевої групи, точно діє на -ому рівні відповідного кореневого дерева. Таким чином, групу такого автомата можна задавати як групу підстановок на множині слів довжини .

У випадку бінарного алфавіту знайдено точну оцінку порядку групи автомата без циклів з виходом. Для автомата з станами порядок його групи не перевищує числа .

Наведено конструкції, що дозволяють конструювати автомати, які породжують вінцевий добуток та прямий степінь за автоматом, що породжує початкову групу. Побудовано серії автоматів без циклів з виходом та знайдено групи, які вони визначають.

За допомогою програмного пакету GAP з точністю до ізоморфізму знайдено повний перелік груп, які можуть бути породжені автоматами без циклів з виходом з 5 станами або менше. Для суттєвого прискорення цих обчислень використовувалась, зазначена вище, можливість задавати групи автомата підстановками.

Для елементів скінченного порядку групи всіх скінченно станових автоморфізмів регулярного кореневого дерева встановлено, що вони спряжені в цій групі тоді і лише тоді, коли вони спряжені в групі всіх автоморфізмів регулярного кореневого дерева, критерій спряженості в якій є відомим. Для елементів нескінченного порядку знайдено зв'язок між їх спряженістю та спряженістю станів їх першого рівня і степенів самих елементів. Також доведено критерій спряженості з додавальною машиною над бінарним алфавітом.

Автор висловлює подяку науковому керівнику Олійнику Андрію Степановичу за постановку задач, обговорення і допомогу при оформленні дисертації.

Список публікацій за темою дисертації

1. Руссєв, А. В. Про скінченні та абелеві групи, породжені скінченними автоматами / А. В. Руссєв // Математичні студії. -- 2005. -- Т. 24, N 2. -- С. 139-146.

2. Руссєв, А. В. Про спряженість у групах скінченностанових автоморфізмів кореневих дерев / А. В. Руссєв // УМЖ. -- 2008. -- Т. 60, N 10. -- С. 1357-1366.

3. Руссєв, А. В. Групи автоматів без циклу з виходом / А. В. Руссєв // Доп. НАН України. -- 2010. -- N 2. -- С. 28-32.

4. Russyev, A. V. Finite groups as groups of automata with no cycles with exit / A. V. Russyev // Algebra and Discrete Mathematics. -- 2010. -- Vol. 9, no. 1. -- Pp. 86-102.

5. Russyev, A. V. Conjugacy of periodic finite state automorphisms / A. V. Russyev // 6th International Algebraic Conference in Ukraine. -- Kamyanets-Podilsky: 2007. -- July 1-7. -- P. 173.

6. Russyev, A. V. Groups of automata without cycles with exit / A. V. Russyev // 7th International Algebraic Conference in Ukraine. -- Kharkov: 2009. -- August 18-23. -- P. 116.

7. Руссєв, А. В. Групи автоматів над скінченним алфавітом / А. В. Руссєв // Український математичний конгрес - 2009. -- Київ: 2009. -- 27-29 серпня. http://www.imath.kiev.ua/~congress2009/Abstracts/Rusev.pdf.

8. Russyev, A. V. Groups of automata with no cycles with exit / A. V. Russyev // Humboldt Cosmos: Science and Society. -- Kiev: 2009. -- November 19-22. -- P. 41.

Анотація

Руссєв А. В. Скінченні підгрупи і спряженість у групах скінченних автоматів. -- Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.06 -- алгебра і теорія чисел. -- Київський національний університет імені Тараса Шевченка, Київ, 2011.

В дисертації досліджується група всіх скінченно станових автоморфізмів регулярного кореневого дерева. В роботі встановлюються умови скінченності самоподібних підгруп цієї групи та умови спряженості елементів в цій групі.

Виділено клас автоматів без циклів з виходом та доведено, що група автомата без циклів з виходом скінченна. Встановлено критерій абелевості групи автомата та доведено, що абелева група автомата буде скінченною тоді і лише тоді, коли автомат не містить циклів з виходом. Для автомата без циклів з виходом з станами за певних додаткових умов доведено точність дії його групи на -ому рівні кореневого дерева. У випадку бінарного алфавіту знайдено точну оцінку порядку групи автомата як функцію від . З точністю до ізоморфізму знайдено повний список груп автоматів без циклів з виходом з 2, 3, 4 та 5 станами.

Доведено критерій спряженості елементів скінченного порядку та критерій спряженості з додавальною машиною над бінарним алфавітом в групі всіх скінченно станових автоморфізмів.

Аннотация

Руссев А. В. Конечные подгруппы и сопряженность в группах конечных автоматов. -- Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.06 -- алгебра и теория чисел. -- Киевский национальный университет имени Тараса Шевченко, Киев, 2011.

В диссертации исследуется группа всех автоморфизмов с конечным числом состояний регулярного корневого дерева. В роботе устанавливаются условия конечности самоподобных подгрупп этой группы и условия сопряженности элементов в этой группе.

Среди групп конечных автоматов выделен класс автоматов без циклов с выходом и доказано, что группа автомата без циклов с выходом конечна. Установлен критерий абелевости группы автомата и доказано, что абелевая группа автомата будет конечной тогда и только тогда, когда она порождается автоматом без циклов с выходом.

Для автомата без циклов с выходом, в каждом из состояний которого реализуется подстановка из некоторой фиксированной абелевой группы, доказано, что его группа действует точно на -ом уровне соответствующего корневого дерева. В случае бинарного алфавита установлено, что порядок группы автомата с состояниями не превышает числа , и эта оценка достигается.

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

С точностью до изоморфизма получен полный список групп автоматов без циклов с выходом с 2, 3, 4 и 5 состояниями. Изначально список был получен с помощью программного пакета GAP. В работе подтверждается принадлежность групп найденному списку (для части групп в случае 5 состояний).

Для элементов конечного порядка группы всех автоморфизмов с конечным числом состояний регулярного корневого дерева установлено, что они сопряжены в этой группе тогда и только тогда, когда они сопряжены в группе всех автоморфизмов регулярного корневого дерева.

Для элементов бесконечного порядка найдена связь между их сопряженностью и сопряженностью их состояний первого уровня и степеней самих элементов. Также получен критерий сопряженности со счетной машиной над бинарным алфавитом.

Annotation

Russyev A. V. Finite subgroups and conjugacy in groups of finite automata. -- Manuscript.

The thesis for obtaining the Candidate of Physical and Mathematical Sciences degree in the speciality 01.01.06 -- algebra and number theory. -- Kiev National Taras Shevchenko University, Kiev, 2011.

For the group of finite state automorphisms of a regular rooted tree it is determined conditions of finiteness of its self-similar subgroups and conditions of conjugacy for some of its elements.

We have defined the class of automata without cycles with exit and proved that the group of an automaton without cycles with exit is finite. We have established the commutativity criterion of automaton group and proved that abelian group of an automaton is finite if and only if this automaton does not contain cycles with exit. For an automaton without cycles with exit with states that satisfies special conditions we have proved that its action on -th level of rooted tree is faithful. In case of binary alphabet we have found precise estimation of the order of automaton group as function of . We have found complete list of pairwise non-isomorphic groups of automata without cycles with exit with 2, 3, 4 and 5 states.

We have proved the conjugacy criterion of elements that have finite order and conjugacy criterion with adding machine over binary alphabet in the group of all finite-state automorphisms.

Размещено на Allbest.ru