Головна Головна -> Реферати українською -> Дисертації та автореферати -> Функції росту автоматів Мілі з двома станами над двоелементним алфавітом та напівгрупИ, що ними породжуються

Функції росту автоматів Мілі з двома станами над двоелементним алфавітом та напівгрупИ, що ними породжуються

Назва:
Функції росту автоматів Мілі з двома станами над двоелементним алфавітом та напівгрупИ, що ними породжуються
Тип:
Реферат
Мова:
Українська
Розмiр:
11,43 KB
Завантажень:
485
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8 
Київський національний університет імені Тараса Шевченка
Резников Ілля Ігоревич
УДК 519.713
Функції росту автоматів Мілі з двома станами над двоелементним алфавітом та напівгрупИ, що ними породжуються
01.01.08 – Математична логіка, теорія алгоритмів та дискретна математика
Автореферат
дисертації на здобуття наукового ступеня кандидата фізико-математичних наук
Київ-2002
Дисертацією є рукопис.
Роботу виконано в Київському національному університеті імені Тараса Шевченка на кафедрі алгебри та математичної логіки.
Науковий керівник доктор фізико-математичних наук, професор
Сущанський Віталій Іванович,
завідувач кафедри алгебри та математичної логіки
Київського національного університету імені Тараса Шевченка
Офіційні опоненти: доктор фізико-математичних наук, професор
Варбанець Павло Дмитрович,
завідувач кафедри комп’ютерної алгебри і дискретної математики
Одеського державного університету імені І.І. Мечникова
кандидат фізико-математичних наук,
Грунський Ігор Сергійович,
старший науковий співробітник лабораторії прикладних проблем дискретної математики
Інституту прикладної математики та механіки НАН України
Провідна установа Інститут кібернетики НАН України імені В.М. Глушкова, відділ теорії цифрових автоматів, м. Київ
Захист відбудеться “16” вересня 2002 р. о 14:00 годині на засіданні спеціалізованої вченої ради Д 26.001.18 Київського національного університету імені Тараса Шевченка за адресою: 03127, м. Київ, проспект академіка Глушкова, 6, Київський національний університет імені Тараса Шевченка, механіко-математичний факультет.
З дисертацією можна ознайомитись у бібліотеці Київського національного університету імені Тараса Шевченка (вул. Володимирська, 58).
Автореферат розісланий “15” липня 2002 р.
Вчений секретар спеціалізованої вченої ради В.В. Плахотник
Загальна характеристика роботи
Актуальність теми. Поняття росту є одним з основних у сучасній комбінаторній алгебрі, і розглядається для багатьох алгебраїчних і геометричних об’єктів. Основною проблемою стосовно росту алгебраїчних об’єктів з того чи іншого класу є визначення можливих функцій росту і дослідження їхніх зв’язків із властивостями об’єктів. В теорію груп поняття росту ввійшло після робіт А.С. Шварца і, особливо, Дж. Мілнора. Дослідження росту напівгруп і автоматів було почато трохи пізніше. У 1968 році Дж. Мілнор і Дж. Вольф встановили, що кожна скінченнопороджена розв’язна група має або поліноміальний, або експоненційний ріст. У своїй чудовій теоремі М. Громов дав опис груп поліноміального росту: кожна така група є скінченним розширенням нільпотентної групи. У 1988 році Р.І. Григорчук одержав аналогічний результат для скінченнопороджених напівгруп зі скороченнями.
Початок вивчення груп і напівгруп автоматних перетворень припадає на 60-ті роки минулого століття. Значною мірою ці дослідження були стимульовані роботами 80-тих років, в яких автомати застосовувалися для побудови груп із тими або іншими екстремальними властивостями: періодичні групи бернсайдового типу (С.В. Альошин, В.І. Сущанський, Р.І. Григорчук, Н. Гупта, С. Сідкі), групи проміжного росту (Р.І. Григорчук, Н. Гупта, Я. Фабриковскі), мінімально нескінченні (just infinite) групи (А. Бранер, С. Сідкі, А. Вієра), вільні групи чи напівгрупи, породжені автоматними перетвореннями, що визначаються одним чи кількома автоматами (С.В. Альошин, А.С. Олійник). Автомати Мілі виявилися зручним способом завдання груп і напівгруп перетворень, оскільки вже невеликі (за кількістю внутрішніх станів та символів алфавіту) автомати можуть породжувати складно влаштовані групи і напівгрупи з цікавими властивостями.
Конструкції груп проміжного росту вперше були запропоновані Р.І. Григорчуком в 1984 році як розв’язання поставленої Дж. Мілнором (1968 р.) проблеми про існування груп проміжного росту. Як показали подальші дослідження, вони можуть бути описані на кількох еквівалентних мовах: автоморфізмів кореневих дерев, ізометрій неархімедових метрик, перетворень, заданих автоматами Мілі.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8 



Реферат на тему: Функції росту автоматів Мілі з двома станами над двоелементним алфавітом та напівгрупИ, що ними породжуються

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок