Анотація до роботи:

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

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

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

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

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

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

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

Публікації автора:

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

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

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

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

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

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