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

УДК 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).

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

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

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

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

охарактеризувати функції росту вказаних напівгруп.

Наукова новизна одержаних результатів. В дисертації отримано такі нові результати:

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

показано, що автомати Мілі з двома станами над двоелементним алфавітом мають 13 попарно різних функцій росту;

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

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

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

Всі результати отримано вперше.

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

Особистий внесок здобувача. Наукові результати, які ввійшли в дисертаційну роботу, одержані здобувачем особисто і самостійно. Зі спільних з професором В.І. Сущанським праць науковому керівнику належить розробка методики досліджень; доведення теорем 3.5 та 4.2 проведено при рівному вкладі авторів.

Апробація результатів роботи. Результати дисертаційної роботи доповідалися і обговорювалися на алгебраїчному семінарі Київського національного університету імені Тараса Шевченка (Київ, 2001), на семінарі з теорії груп та напівгруп при механіко-математичному факультеті (Київ, 2000-2001), на Третій міжнародній алгебраїчній конференції в Україні (Суми, 2001), на семінарі відділу теорії цифрових автоматів Інституту кібернетики НАН України імені В.М. Глушкова (Київ, 2002), на семінарі лабораторії прикладних проблем дискретної математики Інституту прикладної математики і механіки НАН України (Донецьк, 2002).

Публікації. Основні результати дисертаційної роботи опубліковано в 6 працях [-], з яких 5 надруковано у фахових виданнях з переліку ВАК України.

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

Основний Зміст дисертації

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

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

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

В другому розділі описується методика дослідження проблеми, розглядаються допоміжні конструкції. Позначимо символом Amxn множину всіх автоматів Мілі з m станами над n-елементним алфавітом. В § 2.1 вводиться спеціальна нумерація автоматів з при фіксованих значеннях параметрів m та n. Спочатку окремо нумеруються функції переходів та виходів, які отримують номери від 0 до mmn – 1 та від 0 до nmn – 1 відповідно. Автомат A=(X,Q,,)отримує номер в межах від 0 до (mn)mn – 1 за формулою, де N(), N() – номери його функцій переходів і виходів відповідно.

Автомат при довільному qQ завдає перетворення fq на множині X* всіх слів в алфавіті X або на множині X всіх -слів (нескінченних вправо слів) над алфавітом X. Напівгрупа SA перетворень множини X* (або X), породжена всіма перетвореннями виду fq, qQ, називається напівгрупою автоматних перетворень, що завдається автоматом A. В разі, коли всі перетворення fq бієктивні, природно визначається група автоматних підстановок, що породжується автоматом A.

Напівгрупа перетворень SA, породжена автоматом A, має природну систему твірних fq, qQ, і можна досліджувати ріст цієї напівгрупи відносно так вибраної системи твірних. Нагадаємо, що ростом напівгрупи S с системою твірних S називається функція така, що (n) дорівнює кількості елементів напівгрупи S, які можуть бути подані у вигляді добутку довжини не більше n твірних із S.

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

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

На множині всіх автоматів, вхідний і вихідний алфавіт яких однакові, вводиться дія множення, що змістовно відповідає послідовному з’єднанню автоматів. Тим самим для кожного автомата при довільному nN визначено його n-тий степінь An=(X,Qn,n,n). Мінімізуючи стандартним чином An, дістанемо автомат A(n)=(X,Q(n),n,n) з такою самою дією, але, можливо, з меншою кількістю станів. Функція називається функцією росту автомата A. Відомо4,6, що для довільного автомату A функція збігається зі сферичною функцією росту напівгрупи SA.

На множині вводиться природне відношення еквівалентності, при якому еквівалентні автомати породжують ізоморфні напівгрупи перетворень. А саме, два автомати Мілі Ai=(X,Q,i,j), i = 1,2, будемо називати еквівалентними, якщо існують перестановка алфавіту X та перестановка множини станів Q такі, що мають місце співвідношення:

та, для усіх xX та qQ.

Автомат такий, що для довільної букви xX та будь-яких станів qi,qjQ має місце рівність, будемо називати виродженим. Легко бачити, що функція росту автомату Мілі A тотожна одиниці тоді і тільки тоді, коли він вироджений.

На основі відомих співвідношень про кількість класів ізоморфних автоматів (див., наприклад), вказано (тв. 2.2 та 2.4) формули для кількості E(n,m) класів введеної вище еквівалентності на, та числа U(n,m) класів еквівалентності, які складаються з вироджених автоматів. Зокрема, E(2,2) = 76 та U(2,2) = 24. Представником класу еквівалентності далі будемо вибирати автомат з найменшим номером в розумінні введеної вище нумерації N. Ясно, що для дослідження напівгруп, які породжуються автоматами з, або при вивченні функцій росту самих автоматів достатньо розглянути невироджені попарно нееквівалентні автомати, кількість яких дорівнює E(n,m) - U(n,m).

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

В § 2.3 докладніше розглядається множина автоматів. Автомати з множини мають 16 різних функцій переходів та 16 різних функцій виходів. Далі ми будемо класифікувати автомати за їх функціями переходів. Згідно з нумерацією N, кожен автомат A має вигляд A=(X,Q,(i),(j)), де i,j=0,1,…,15, і йому відповідає номер NA = 16i + j. Максимальна кількість невироджених попарно нееквівалентних автоматів в дорівнює E(2,2) - U(2,2) = 52. В 2.3.1 вибрано представників класів еквівалентності, які досліджуються в третьому та четвертому розділах.

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

Слід зазначити, що більшість напівгруп, що породжуються автоматами (майже) сталого росту, легко можуть бути сконструйовані виходячи з напівгрупи перетворень двоелементної множини та її піднапівгруп. Максимальний порядок напівгрупи з цього класу дорівнює 7, а кількість попарно неізоморфних напівгруп – 15.

В множині існує 10 попарно нееквівалентних автоматів лінійного росту, які розглянуто в § 3.2 та § 3.3. В § 3.2 розглядаються чотири необоротні автомати, які породжують напівгрупи лінійного росту. Ці автомати мають дві функції росту: A(n)=n+1 та A(n)=2n, n..1.

В § 3.3 досліджуються обидва автомати лінійного росту, які породжують напівгрупи квадратичного росту.

Теорема 3.4. Автомати A77=(X,Q,(4),(13)) та A81=(X,Q,(5),(1)) мають функцію росту, , а породжені ними напівгрупи та мають функцію росту,.

Чотири автомати лінійного росту, що залишилися, є оборотними. Групи перетворень, що ними породжуються, досліджено в роботі Р.І. Григорчука, В.В. Некрашевича, В.І. Сущанського6.

В § 3.4 розглянуто єдиний клас еквівалентності автоматів проміжного росту, що складається з чотирьох автоматів, та встановлено його основні властивості. Кожен з цих еквівалентних між собою автоматів є найменшим можливим (за кількістю станів і символів алфавіту) автоматом Мілі проміжного росту. Позначимо Rp,m – кількість всіх розбиттів натурального числа p на m додатних доданків, а Rp – кількість всіх розбиттів натурального числа p на натуральні доданки.

Теорема 3.5. Автомат A24=(X,Q,(1),(8)) має такі властивості:

Напівгрупа задається твірними та визначальними співвідношеннями таким чином:

Функція росту напівгрупи визначається співвідношенням:

Наслідок 3.1. Функція має проміжний порядок росту, причому

В четвертому розділі розглядаються 17 класів еквівалентності автоматів експоненційного росту з множини, автомати з яких мають 5 попарно різних функцій росту. В § 4.1 розглянуто автомати, які породжують напівгрупи експоненційного росту, що не є вільними. Значення функцій росту автоматів визначаються через рекурентні послідовності G(n) та H(n), які задаються таким чином:

G(n)=G(n-2)+G(n-3),; початкові умови G(0)=1, G(1)=1, G(2)=1.

H(n)=H(n-1)+H(n-2)+H(n-4),; початкові умови H(0)=1, H(1)=2, H(2)=4, H(3)=7.

Теорема 4.1. Автомати A75=(X,Q,(4),(11)) та A88=(X,Q,(5),(8)) породжують напівгрупи, що задаються твірними та визначальними співвідношеннями таким чином:

Функції росту цих автоматів та напівгруп, які ними породжуються, визначаються через елементи послідовності G(n) рівностями:

Теорема 4.2. Автомати A66=(X,Q,(4),(2)), A67=(X,Q,(4),(3)), A72=(X,Q,(4),(8)), A78=(X,Q,(4),(14)) та A82=(X,Q,(5),(2)) мають функцію росту а породжені ними напівгрупи

мають функцію росту

Теорема 4.3. Автомат A76=(X,Q,(4),(12)) має функцію росту

Автомати, які породжують вільну напівгрупу перетворень, розглядаються в § 4.2. Задача побудови вільних груп та напівгруп автоматних перетворень вже має певну історію. Вперше приклад автоматів, які породжують вільну групу, було запропоновано в роботі Альошина. Проте доведення в цій роботі були неповними і конструкція на даний час не обґрунтована. Перші приклади вільних груп і напівгруп автоматних перетворень з повним доведенням було запропоновано в роботах Олійника (1998). Але в цих роботах використовуються автомати, в яких число станів чи символів алфавіту більше двох. Виявляється, що існує 9 класів еквівалентності на, автомати з яких породжують вільну напівгрупу перетворень. Всі ці автомати мають функції переходів або, і охарактеризовані в таких твердженнях.

Теорема 4.4. Автомати A83=(X,Q,(5),(3)), A86=(X,Q,(5),(6)) та A92=(X,Q,(5),(12)) породжують вільну напівгрупу перетворень.

Теорема 4.5. Довільний невироджений автомат A з функцією переходів породжує вільну напівгрупу перетворень.

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

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

Висновки

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

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

Показано, що автомати Мілі з двома станами над двоелементним алфавітом мають 13 попарно різних функцій росту, з яких 5 є майже сталими, 2 – лінійними функціями, одна має проміжний порядок росту, і 5 – експоненційний. Доведено, що автомати з породжують 27 попарно неізоморфних напівгруп, які не є групами, причому серед них є напівгрупи (майже) сталого, лінійного, квадратичного, проміжного та експоненційного росту.

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

список опублікованих робіт за темою дисертації

Резников І.І. Вільні напівгрупи перетворень, породжені автомата-ми з двома станами // Вісн. Київ. Універ. Сер. фіз.-мат.наук. – 2001. – №2. – С. 86-91.

Резников І.І. Автомати Мілі з двома станами над двоелементним алфавітом, які породжують вільну напівгрупу // Вісн. Київ. Універ. Сер. фіз.-мат.наук. – 2001. – №3. – С. 58-65.

Резников І.І. Автомати Мілі з двома станами над двоелементним алфавітом, які породжують скінченні напівгрупи перетворень // Вісн. Київ. Універ. Сер. фіз.-мат.наук. – 2001. – №4. – С. 78-86.

Резников И.И., Сущанский В.И. Функции роста автоматов с двумя состояниями над двухэлементным алфавитом // Доп. НАН України. – 2002. – №2. – С. 76-81.

Reznykov I.I, Sushchansky V.I. 2-generated semigroup of automatic transformations, whose growth is defined by Fibonacci series // Матем. студ. – 2002. – 17, №1. – С. 81-92.

Резников И.И., Сущанский В.И. О функциях роста полугрупп, определенных автоматами Мили с двумя состояниями над двухбуквенным алфавитом // Пр. Трет. Міжнар. Алгебр. конфер. в Україні. – Суми. – 2001. – С. 238-239.

Анотації

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

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

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

Ключові слова: скінченний автомат Мілі, функція росту, напівгрупа автоматних перетворень, поліноміальний ріст, проміжний ріст, експоненційний ріст, вільна напівгрупа.

Резников И.И. Функции роста автоматов Мили с двумя состояниями над двухэлементным алфавитом и полугруппы, которые ими порождаются. – Рукопись.

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

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

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

Reznykov I.I. The growth functions of two-state Mealy automata over a two-symbol alphabet and the semigroups, defined by them. – Manuscript.

A thesis for a doctor’s degree by specialty 01.01.08 – mathematical logic, theory of algorithms and discrete mathematics. – Kyiv Taras Schevchenko University, Kyiv, 2002.

The dissertation paper is devoted to research of the growth functions of two-state Mealy automata over a two-symbol alphabet and the semigroups of automatic transformations, defined by these automata. The growth functions of the specified Mealy automata are calculated, the semigroups defined by these automata are described in terms of generators and defining relations, their growth functions are computed and the main properties of these automatic transformation semigroups are researched.

Let’s denote by the symbol the set of two-state Mealy automata over a two-symbol alphabet. An equivalence relation on the set such, that the equivalent automata define isomorphic semigroups of transformations, is introduced. Using this equivalence relation and concept of degenerated automata (an automaton is said to be degenerated, if its output function defines the same output for all states of an automaton), it is shown that it is enough to study just 52 non-degenerated pairwise non-equivalent automata instead of all 256 automata of the set. The program complex for investigations of the growth functions of Mealy automata and automatic transformation semigroups was developed. Using this complex, initial values and finite differences of the growth functions, and some properties of the transformation semigroups, defined by automata from the set, were calculated. The results of the computational experiments have allowed putting forward working hypotheses about the growth functions of these automata. The dissertation paper contains description of the structure of this program complex, its main modules, the principles of functioning, and supplementary mathematical constructions.

The following results are obtained in the dissertation paper about the growth functions of two-state Mealy automata over a two-symbol alphabet and the automatic transformation semigroups, defined by them:

Automata from the set have 13 pairwise different growth functions. The minimal function is the growth function that is identically equal to one, and the maximal one is the exponential function 2n. Five functions are almost constant, two are linear functions, one function has intermediate growth, and five are the functions of exponential growth.

These automata define 27 pairwise nonisomorphic semigroups that are not groups. All these semigroups are described in terms of generators and defining relations. Among them there are semigroups of finite, linear, square, intermediate and exponential orders of growth.

The growth functions of all automata from and the automatic transformation semigroups, defined by them, are calculated. The growth function of intermediate growth order is determined through a number of partitions of a natural number to the positive items, and all growth functions of exponential growth are described by linear recurrent relations.

Four pairwise equivalent Mealy automata has intermediate growth and are the least possible Mealy automata of intermediate growth. They define the semigroup of intermediate growth that is a monoid and has infinite set of defining relations.

All automata from the set, that have linear growth, but define semigroups of square growth, are described. All non-invertible two-state automata over a two-symbol alphabet, that defining semigroups of exponential growth with nontrivial defining relations, and automata from the set that define free semigroup, are characterized.

Keywords: a finite Mealy automaton, the growth function, an automatic transformation semigroup, polynomial growth, intermediate growth, exponential growth, a free semigroup.