LibRar.Org.Ua — Бібліотека українських авторефератів

Загрузка...

Головна Електроніка. Обчислювальна техніка → Функції росту автоматів Мілі з двома станами над двохелементним алфавітом та напівгрупи, що ними породжуються

11


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











Резников Ілля Ігоревич





УДК 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 р.) проблеми про існування груп проміжного росту. Як показали подальші дослідження, вони можуть бути описані на кількох еквівалентних мовах: автоморфізмів кореневих дерев, ізометрій неархімедових метрик, перетворень, заданих автоматами Мілі. Це стало стимулом для розвитку досліджень з теорії автоматних перетворень, метою яких, зокрема, була побудова автоматів Мілі, що визначають нові групи і напівгрупи проміжного росту. В результат автомати проміжного росту із m станами над n-елементним алфавітом були побудовані для всіх допустимих пар (m,n) таких, що або , або . Слід зазначити, що напівгрупи проміжного росту можуть мати додаткові властивості, які не мають аналогів в теорії груп. Так, наприклад, проміжний ріст можуть мати лінійні напівгрупи над полями, відносно вільні напівгрупи нільпотентних многовидів, тощо. В зв’язку з цим проф. Р.І. Григорчук в своїй пленарній доповіді на Першій міжнародній алгебраїчній конференції в Україні (Слов’янськ, 1997 р.) поставив задачу дослідження функцій росту всіх автоматів Мілі з двома станами над двоелементним алфавітом та напівгруп перетворень, ними породжених.

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

Задачі алгебраїчної теорії автоматів та пов’язані з ними задачі комбінаторної алгебри, як правило, вимагають великого об’єму обчислень, оскільки відповідні алгоритми в загальному випадку мають експоненційну часову складність. Наприклад, обчислення функції росту автомату Мілі пов’язано з мінімізацією його степенів, а стандартні алгоритми мінімізації є експоненційними. А тому широкі обчислювальні експерименти для досліджень в цій галузі можливі лише за допомогою програмних комплексів. На даний час використовуються програмні комплекси як загального застосування, наприклад, MathCAD, Mathematica, Statistica, так і більш спеціалізовані, наприклад, GAP для абстрактної теорії груп, SINGULAR для поліноміальних обчислень, методів алгебраїчної геометрії, гомологічної алгебри, і т.д. Так як спеціалізованого програмного комплексу з широкими можливостями для досліджень в алгебраїчній теорії автоматів ще не розроблено, то створення таких комплексів є актуальною задачею.

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

Зв’язок роботи з науковими програмами, планами, темами. Тематика дисертаційної роботи пов’язана з науково-дослідницькими роботами кафедри алгебри та математичної логіки Київського національного університету імені Тараса Шевченка „Комбінаторно-геометричні, категорні та комп’ютерні методи вивчення алгебраїчних структур та їх зображень” (номер державної реєстрації 0101U002484).

Мета і задачі дослідження. Метою дисертації є:

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

знайти функції росту автоматів Мілі з двома станами над двоелементним алфавітом;

описати в термінах твірних і визначальних співвідношень напівгрупи автоматних перетворень, які породжуються автоматами Мілі з двома станами над двоелементним