Мучнікова Л.А. Контрольні експерименти з груповими автоматами. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики. – Інститут кібернетики імені В.М.Глушкова НАН України, Київ, 2006.
Дисертаційну роботу присвячено дослідженню структурних, складностевих та алгоритмічних властивостей контрольних експериментів відносно нескінченного класу групових автоматів. Введено новий тип експериментів з автоматами, так звані контрольні розмічені експерименти, які узагальнюють класичні контрольні експерименти і існують у випадку нескінченних класів автоматів. Показана можливість редукції нескінченної множини розмічених експериментів до так званих циклічних експериментів і доведений відповідний критерій для контрольних експериментів. Запропоновано новий спосіб задання автомату у вигляді визначальної пари множин циклічних слів автомату і знайдено зв’язок визначальної пари з алгебраїчними властивостями автомата. Доведено теореми характеризації контрольних циклічних експериментів, які зв’язують їх з визначальними парами, спеціальними груповими замиканнями фрагментів поведінки, фрагментами інформаційних дерев автоматів. Отримано досяжні оцінки кратності та довжини мінімальних контрольних циклічних експериментів, вперше для такого типу оцінок знайдено множину можливих значень довжини таких експериментів в залежності від параметрів автомату. Розроблено алгоритми побудови мінімальних контрольних циклічних експериментів і знайдено оцінку їх складності, а також розроблено алгоритми побудови визначальних пар, синтезу автомату по визначальній парі, яка його задає, рекурсивного алгоритму побудови визначальних співвідношень опорної групи автомату.
У роботі введено і обґрунтовано новий підхід до розширення можливостей контрольних експериментів для групових автоматів. Досліджено можливості контрольних експериментів при введені у вхід-вихідні слова мінімальної додаткової інформації про внутрішні стани автомату. Досліджено умови, за яких такі експерименти є контрольними. Встановлено взаємозв’язок між структурою графа автомату і його алгебраїчними властивостями і структурою контрольних експериментів.
Одержано наступні результати:
введено новий вид експериментів з автоматами – контрольні розмічені експерименти, які узагальнюють класичні, розширюють їх можливості і області їх існування;
запропоновано скінченне задання нескінченного класу еквівалентних за розрізняючими здатностями розмічених експериментів – циклічні експерименти;
розроблено метод аналізу циклічних експериментів і на його основі знайдено критерій (тобто необхідні та достатні умови) в термінах запропонованої операції групового замикання, за яким розмічений експеримент є контрольним;
запропоновано нове задання групового автомата визначальною парою множин його циклічних слів, аналогічне класичному заданню автоматів визначальними співвідношеннями; вирішено задачу задання групового автомата визначальною парою і зворотню – побудови за нею автомата;
знайдено критерій в термінах визначальних пар, при якому розмічений експеримент є контрольним;
розроблено техніку розмічених дерев, що є основним засобом аналізу, синтезу і оцінок складності розмічених експериментів;
отримано досяжні оцінки кратності та довжини мінімальних контрольних циклічних експериментів, вперше для такого типу оцінок отримано опис поведінки функції довжини;
розроблено поліноміальні алгоритми побудови оптимальних контрольних циклічних експериментів і визначальних пар автоматів, а також алгоритми синтезу автомату за заданою парою і побудови визначальних співвідношень опорної групи автомату.
Результати є новими і завершеними. Вперше отримано критерії, які описують структуру введених розмічених експериментів, знайдено точні оцінки їх параметрів, розроблені і реалізовані алгоритми їх побудови. Вони підтверджують правомірність і доцільність розробленого підходу.
Публікації автора:
Толмачевская Л.А. Циклические представления групповых автоматов. // Труды института прикладной математики и механики. – 2000. – Т. 5. – С. 145 – 154.
Козловский В.А., Толмачевская Л.А. Построение множества определяющих слов опорной группы конечного группового автомата. // Вісник Донецького університету, серія А: Природничі науки, Вип.2 – 2001. – С. 357 – 363.
Толмачевская Л.А. Контрольные циклические эксперименты с групповыми автоматами. // Кибернетика и системный анализ. – 2005. – № 3 – С. 32 – 46.
Толмачевская Л.А. О нижних оценках длины контрольных циклических экспериментов. // Труды института прикладной математики и механики.– 2005.– Т.10.– С.214–223.
Толмачевская Л.А. Алгоритмы построения контрольных циклических экспериментов с групповыми автоматами. // Труды института прикладной математики и механики.– 2006. – Т.12.– С. 178–193.
Козловский В.А., Толмачевская Л.А. О контроле автоматов циклическими экспериментами. // Компьютерные науки и информационные технологии. Тезисы докладов международной конференции, посвященной памяти проф. А.М.Богомолова (Саратов, 14–18 мая 2002 г.). – Саратов: Изд-во Сар. ун-та, 2002. – С.33 – 34.
Козловский В.А., Толмачевская Л.А. Эксперименты с групповыми автоматами на основе определяющих соотношений. // Труды третьей международной научно-практической конференции «Современные информационные и электронные технологии» (Одесса, 21–24 мая 2002 г.). – Одесса, 2002. – С.101.
Толмачевская Л.А. Циклические эксперименты с групповыми автоматами // Проблемы теоретической кибернетики. Тезисы докладов XIII Международной конференции (Казань, 27–31 мая 2002 г.). – Казань, 2002. – С.177.
Козловский В.А., Толмачевская Л.А. Задача идентификации автоматов в классе// Матеріали міжнародної конференції з управління "Автоматика-2002" (Донецьк, 16–20 вересня 2002 р.) – Т.1 – Донецьк, 2002. – С.125.
Козловский В.А., Толмачевская Л.А. Построение множества определяющих слов опорной группы по определяющей паре конечного группового автомата. // Всеукраїнська конференція. Алгебраїчні методи дискретної математики (теорія та методологія) в ЛДПУ ім. Т.Шевченка. (Луганськ, 23–27 вересня 2002 р.). – Луганськ: Alma Mater, 2002. – С.71 – 72.
Толмачевская Л.А. Циклические эксперименты с автоматами и их сложность// Материалы VIII Международного семинара "Дискретная математика и ее приложения" (Москва, 2–6 февраля 2004 г.). – Москва, 2004. – С. 317 – 321.
Толмачевская Л.А. Метод деревьев для получения оценок контрольных экспериментов с групповыми автоматами // VI Международная Конференция "Дискретные модели в теории управляющих систем” (Москва, 7–11 декабря 2004 г.). – Москва, 2004. – С. 144 – 147.
V.A.Kozlovskii, L.A.Tolmachevskaya Metric characteristics of set of generators of finite index subgroup of free finitely generated group // 5th International algebraic conference in Ukraine. Abstracts (Odessa, July 20–27, 2005) – Odessa,2005. – P. 111.
