Дослідження структурних та метричних властивостей систем визначальних співвідношень для повністю визначених та часткових скінчених ініціальних автоматів. Взаємозв’язок між структурою графа автомата та структурою його систем визначальних співвідношень.
Аннотация к работе
В.М.Глушков запропонував розглядати таку систему як систему двох взаємодіючих автоматів. В.М.Глушков, Ю.В.Капітонова, О.А.Летичевський запропонували розглядати проектування обчислювальних систем як поетапний процес розробки системи “згори донизу”. І.С.Грунський, Р.І.Олійник, Л.А.Толмачевська показали, що системи визначальних співвідношень можуть бути ефективно застосовані при побудові експериментів зі скінечними автоматами та іншими моделями скінчених дискретних систем. Дослідження по проблемі дисертаційної роботи проводилися у відповідності з планами наукових досліджень відділу теорії керуючих систем ІПММ НАН України та кафедри алгебри Словянського державного педагогічного університету по темах №0104u000863 “Алгебраїчні, комбінаторні, логічні та еволюційні методи дослідження дискретних та безперервних систем та їх застосування до задач ідентифікації та керування”, №0204u000771 “Дослідження актуальних проблем моделювання, керування та ідентифікації дискретних систем”. ініціальний автомат граф вперше знайдено критерій (в термінах структури автомата), за яким скінчене бінарне відношення на вхідних словах є системою визначальних співвідношень для цього автомата;У підрозділі 2.1 викладено алгоритм побудови так званої канонічної системи визначальних співвідношень, оцінено число і складність таких систем. Нехай і - канонічні системи визначальних співвідношень одного і того ж автомата для різних лінійних порядків , на . Нехай - скінчена система визначальних співвідношень для автомата , і - деяке скінчене бінарне відношення на множині . є системою визначальних співвідношень для тоді і лише тоді, коли для будь-якого лінійного порядку на . Однією з класичних проблем, повязаних із зображенням автоматів системами визначальних співвідношень, є проблема ізоморфізма: нехай два автомата і задані скінченими системами визначальних співвідношень; треба знайти алгоритм, який дозволяє визначити, чи є дані автомати ізоморфними. У підрозділі 2.3 запропоновано процедури переходу від системи визначальних співвідношень до обходу та від обходу до системи визначальних співвідношень і розглянуто взаємозвязки між множиною обходів автомата та множиною його систем визначальних співвідношень.Роботу присвячено дослідженню структурних і метричних властивостей систем визначальних співвідношень для повністю визначених і часткових ініціальних скінчених автоматів.
План
ОСНОВНИЙ ЗМІСТ
Вывод
Роботу присвячено дослідженню структурних і метричних властивостей систем визначальних співвідношень для повністю визначених і часткових ініціальних скінчених автоматів.
Список литературы
· вперше знайдено мінімальну так звану канонічну систему визначальних співвідношень та розглянуто її структуру;
· вперше знайдено критерій, за яким скінчене бінарне відношення є системою визначальних співвідношень для заданого скінченого повністю визначеного автомата;
· показано звязок класу систем визначальних співвідношень для даного автомата з іншими його властивостями (базисами досяжності, обходами); запропоновані процедури переходу від обходу до системи визначальних співвідношень і навпаки;
· вперше введено поняття визначальної системи для часткових автоматів, яке узагальнює поняття системи визначальних співвідношень для повністю визначених автоматів; знайдено мінімальну визначальну систему для часткового автомата і досліджено її структуру;
· вперше знайдені необхідні та достатні умови, за яких система є визначальною для деякого часткового, можливо нескінченого автомата; для деякого скінченого автомата; для заданого скінченого автомата.
Ці результати є новими и завершеними.
Таким чином вперше повністю розвязано проблему характеризації скінчених систем визначальних співвідношень для скінчених ініціальних автоматів.
СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1. Грунский И.С., Сенченко А.С. Каноническая система определяющих соотношений для автоматов. // Труды института прикладной математики и механики НАН Украины, - 2002, - т. 7. - с.58-63.
2. Грунский И.С., Сенченко А.С. Каноническая система определяющих соотношений для автоматов. // Компьютерные науки и информационные технологии. Тезисы докладов международной конференции, посвященной памяти проф. А.М.Богомолова (Саратов, 14-18 мая 2002 г.). - Саратов: Изд-во Сар. ун-та, 2002г., с.24-25.
3. Грунский И.С., Сенченко А.С. Свойства систем определяющих соотношений для автоматов. // Дискретная математика, - 2004,- т.16, №4. - с.79-87.
4. Сенченко А.С. Алгебраическое представление частичных автоматов без выхода. // Материалы VIII Международного семинара "Дискретная математика и ее приложения" (2-6 февраля 2004 г.). - М.: Изд-во мехмат. ф-та МГУ, 2004г., с.307-310.
5. Сенченко А.С. Каноническая определяющая система для частичного автомата. // Дискретные модели в теории управляющих систем: VI Международная конференция: Москва, 7-11 декабря 2004 г. Труды. - М.: Изд. отдел ф-та ВМИК МГУ им. Ломоносова, 2004г., с.140-143.
6. Сенченко А.С. Определяющая система для частичных автоматов. // Вісник Донецького університету, серія А: Природничі науки, Вип.1 - 2003. - с.345-350.
7. Сенченко А.С. Построение систем определяющих соотношений для автомата. // Всеукраїнська конференція. Алгебраїчні методи дискретної математики (теорія та методологія) в ЛДПУ ім. Т.Шевченка. (Луганськ, 23-27 вересня 2002 р.). - Луганськ: Alma Mater, 2002р., с.82-83.
8. Сенченко А.С. Построение систем определяющих соотношений для автомата. // Труды V Международной конференции "Дискретные модели в теории управляющих систем" (Ратмино, 26-29 мая 2003 г.). - М.: Изд. отдел ф-та ВМИК МГУ им. Ломоносова, 2003г., с.82-83.
9. Сенченко А.С. Свойства определяющих систем для частичных автоматов. // Труды института прикладной математики и механики НАН Украины, - 2003, - т. 8. - с.111-119.