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

Загрузка...

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

алфавітом;

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

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

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

показано, що автомати Мілі з двома станами над двоелементним алфавітом мають 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,p,l)отримує номер в межах від 0 до (mn)mn – 1 за формулою, де N(p), N(l) – номери його функцій переходів і виходів відповідно.

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

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

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

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

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

На множині вводиться природне відношення еквівалентності, при якому еквівалентні автомати породжують ізоморфні напівгрупи перетворень. А саме, два автомати Мілі Ai=(X,Q,pi,lj), i = 1,2, будемо називати еквівалентними, якщо існують перестановка x алфавіту X та перестановка q множини станів 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 різних функцій виходів. Далі ми будемо класифікувати автомати за їх функціями переходів