НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ КІБЕРНЕТИКИ ІМЕНІ В.М.ГЛУШКОВА

СЕНЧЕНКО ОЛЕКСІЙ СЕРГІЙОВИЧ

УДК 519.7

ЗОБРАЖЕННЯ АВТОМАТІВ ЗА ДОПОМОГОЮ ВИЗНАЧАЛЬНИХ СПІВВІДНОШЕНЬ ЇХ ПОВЕДІНКИ

01.05.01 - “Теоретичні основи інформатики та кібернетики"

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Київ - 2005

Дисертацією є рукопис.

Робота виконана в Інституті прикладної математики і механіки НАН України, м. Донецьк та Слов’янському державному педагогічному університеті Міністерства освіти та науки України.

Науковий керівник: кандидат фіз-мат. наук, с.н.с

Грунський Ігор Сергійович,

доцент кафедри алгебри,

Слов’янський державний педагогічний університет.

Офіційні опоненти: доктор фіз-мат. наук, професор

Капітонова Юлія Володимирівна,

зав. відділом,

Інститут кібернетики ім. В.М.Глушкова НАН України, м.Київ

кандидат фіз.-мат.наук,

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

керівник відділу компютерних технологій,

ТОВ “ІКС 5 лтд”, м.Київ.

Провідна установа: Київський національний університет ім. Т.Шевченка

факультет кібернетики,

кафедра теоретичної кібернетики.

Захист відбудеться 23.09.2005 р. о14 годині на засіданні спеціалізованої вченої ради Д26.194.02 в Інституті кібернетики ім. В.М.Глушкова НАН України за адресою: 03680, м. Київ, просп. Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві Інституту кібернетики ім. В.М.Глушкова НАН України за адресою: 03680, м. Київ, просп. Глушкова, 40.

Автореферат розіслано 22.08.2005 р.

Вчений секретар спеціалізованої

вченої ради Д26.194.02,

кандидат фіз-мат. наук, с.н.с. В.Ф. Синявський

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Теорія скінчених автоматів є одним з найстаріших і найрозвинутіших розділів теоретичної інформатики. Автомати широко використовуються при побудові обчислювальних систем. В.М.Глушков запропонував розглядати таку систему як систему двох взаємодіючих автоматів. В.М.Глушков, Ю.В.Капітонова, О.А.Летичевський запропонували розглядати проектування обчислювальних систем як поетапний процес розробки системи “згори донизу”. На кожному етапі такої розробки роглядається алгебраїчно-автоматне зображення майбутньої обчислювальної системи. Такий підхід успішно реалізовано в Інституті кібернетики НАН України. Наразі тенденцією при такій розробці є сумісне створення обчислювальної системи та засобів її перевірки (веріфікації, тестування) на всіх етапах. При цьому дослідження та створення засобів перевірки відстає від дослідження та створення засобів синтезу систем. Тому створення засобів перевірки є актуальною і важливою задачею. Воно потребує розробки ефективних математичних методів. В наш час інтенсивно розвиваються методи, що засновані на теорії експериментів з автоматами. Одним з таких методів є зображення і дослідження автоматів за допомогою системи визначальних співвідношень. Ю.І.Соркін довів алгоритмічну розв’язність відомих проблем Туе для автоматів. Тим самим було показано принципіальну можливість використання систем визначальних співвідношень при розв’язанні різноманітних задач теорії автоматів. І.С.Грунський, Р.І.Олійник, Л.А.Толмачевська показали, що системи визначальних співвідношень можуть бути ефективно застосовані при побудові експериментів зі скінечними автоматами та іншими моделями скінчених дискретних систем. Для побудови оптимальних експериментів актуальною є задача дослідження структурних та складносних властивостей систем визначальних співвідношень. На наш погляд, цій задачі до цього часу не було приділено достатньо уваги. Ці дослідження служитимуть основою для створення ефективних засобів перевірки обчислювальних систем.

Зв'язок роботи з науковими програмами, планами, темами. Дослідження по проблемі дисертаційної роботи проводилися у відповідності з планами наукових досліджень відділу теорії керуючих систем ІПММ НАН України та кафедри алгебри Слов’янського державного педагогічного університету по темах №0104u000863 “Алгебраїчні, комбінаторні, логічні та еволюційні методи дослідження дискретних та безперервних систем та їх застосування до задач ідентифікації та керування”, №0204u000771 “Дослідження актуальних проблем моделювання, керування та ідентифікації дискретних систем”.

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

Відповідно до цієї мети в роботі ставляться такі задачі:

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

- знайти мінімальні системи визначальних співвідношень для заданого автомата;

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

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

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

- вперше знайдено мінімальну так звану канонічну систему визначальних співвідношень та розглянуто її структуру;

- вперше знайдено критерій (в термінах структури автомата), за яким скінчене бінарне відношення на вхідних словах є системою визначальних співвідношень для цього автомата;

- показано звязок класу систем визначальних співвідношень для даного автомата з іншими його властивостями (базисами досяжності, обходами); запропоновано процедури переходу від обходу до системи визначальних співвідношень і навпаки;

- поняття та апарат систем визначальних співвідношень розповсюджено на всі скінчені (в тому числі на часткові) автомати; знайдено мінімальну визначальну систему для часткового автомата та досліджено її структуру;

- знайдені необхідні та достатні умови, за яких система є визначальною для деякого часткового, можливо нескінченого автомата; для деякого скінченого автомата; для заданого автомата.

Ці результати отримано вперше. Результати є завершеними і строго доведеними.

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

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

Апробація результатів дисертації. Основні результати роботи доповідалися та обговорювалися на:

· Третій міжнародній алгебраїчній конференції в Україні (Суми, 2001);

· Міжнародній конференції, присвяченій пам’яті професора А.М.Богомолова (Саратов, 2002);

· Всеукраїнській конференції “Алгебраїчні методи дискретної математики (теорія та методологія)” (Луганськ, 2002);

· V Міжнародній конференції "Дискретные модели в теории управляющих систем" (Ратміно, Росія, 2003);

· VIII Міжнародному семінарі "Дискретная математика и ее приложения" (Москва, 2004);

· VI Міжнародній конференції "Дискретные модели в теории управляющих систем" (Москва, 2004);

· семінарах відділу теорії керуючих систем і лабораторії дискретної математики і прикладної алгебри Інституту прикладної математики і механіки НАН України (2001-2005);

· семінарі відділу теорії цифрових автоматів Інституту кібернетики імені В.М.Глушкова НАН України (2004-2005);

· семінарах кафедри алгебри Слов’янського державного педагогічного університету (2001-2005);

· семінарах кафедри алгебри Луганського державного педагогічного університету (2001-2004).

Публікації. Основні результати дисертації опубліковано в 9 роботах, з яких 4 є статтями у фахових періодичних виданнях, затверджених ВАК України, 5 є тезами доповідей конференцій.

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

ОСНОВНИЙ ЗМІСТ

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

У першому розділі наводяться необхідні теоретичні відомості і робиться огляд літератури, що відноситься до теми дисертації.

Розглядаються детерміновані, ініціально-зв’язні автомати без виходу , де – множина станів, – алфавіт вхідних символів, – функція переходів і – початковий стан. Автомат породжує на праву конгруенцію за правилом: , якщо , визначені і . Нехай – деяке бінарне відношення на . Це відношення назвемо системою визначальних співвідношень для , якщо , де – правоконгруентне замикання , тобто найменьша права конгруенція, що містить .

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

У підрозділі 2.1 викладено алгоритм побудови так званої канонічної системи визначальних співвідношень, оцінено число і складність таких систем.

Нехай і – довільно зафіксований лінійний порядок на . На вводиться лінійний порядок :

1) ;

2) якщо , то , де - довжина слова ;

3) , якщо для деякого , в той час як .

Нехай і найкоротше за введеним порядком слово, для якого . Множину назвемо найкоротшим за базисом досяжності автомата . Визначимо скінчене бінарне відношення на множині за таким правилом: нехай спочатку порожнє. Для кожних і , якщо і , то пара міститься в .

Теорема 2.1. є системою визначальних співвідношень для автомата .

Оскільки при фіксованому порядку на базис визначається однозначно, то систему визначальних співвідношень назвемо канонічною для автомата .

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

Теорема 2.2. , причому ці оцінки є досяжними для всіх .

Теорема 2.3. , причому ці оцінки є досяжними для всіх .

Кожній скінченій системі визначальних співвідношень автомата поставимо у відповідність дві характеристики. Через позначимо число пар

слів у , а через позначимо , де підсумовування

відбувається за всіма . Значення цих характеристик для довільної канонічної системи визначальних співвідношень автомата , у якого і задовольняють співвідношенням (теореми 2.4 – 2.6) є:

а) ;

б),

де , причому ця оцінка є досяжною для всіх ;

в), причому ця оцінка є досяжною для всіх , .

Нехай і – канонічні системи визначальних співвідношень одного і того ж автомата для різних лінійних порядків , на .

Твердження 2.1. і .

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

Нехай – деяке скінчене бінарне відношення на і – деякий довільно фіксований лінійний порядок на .

Введемо на такі операції:

1. Видалимо з всі пари типу .

2. Кожну пару при замінимо парою .

3. Нехай , . Якщо для деякого , то пару в замінюємо парою . Якщо ж , то пару в замінюємо парою .

4. Видалимо пари, що повторюються, залишаючи тільки по одному екземпляру.

Введемо процедуру редукції відношення , яка складається з таких кроків:

а) виконується операція 1;

б) виконується операція 2;

в) якщо операцію 3 неможливо застосувати до жодної пари, то процедура завершується, інакше після кожного одноразового виконання операції 3 переходимо до кроку (г);

г) виконується операція 4, і переходимо до кроку (а).

Результат редукції позначимо через . Показано (наслідок 2.2.1), що процедура редукції визначає результат однозначно.

Вперше отримано критерій, чи є задане скінчене бінарне відношення системою визначальних співвідношень для заданого автомата .

Теорема 2.7. Нехай – деякий довільно зафіксований лінійний порядок на . тоді і лише тоді, коли .

З теореми 2.7 одержані корисні наслідки.

Наслідок 2.7.1. Нехай – скінчена система визначальних співвідношень для автомата , і – деяке скінчене бінарне відношення на множині . є системою визначальних співвідношень для тоді і лише тоді, коли для будь-якого лінійного порядку на .

Наслідок 2.7.2. Кожна канонічна система визначальних співвідношень є мінімальною (по числу пар і по сумарній довжині слів) системою визначальних співвідношень для .

Теорема 2.7 дозволяє розглянути структуру бінарного відношення . Кожному скінченому бінарному відношенню поставимо у відповідність множину всіх початкових відрізків з , де – множина власних початкових відрізків усіх слів множини .

Наслідок 2.7.3. Нехай – скінчена система визначальних співвідношень для деякого скінченого повністю визначеного автомата з станами. Тоді для будь-якого лінійного порядку на .

Для довільного слова через позначимо найкоротше за слово з .

Наслідок 2.7.4. Нехай . Тоді і .

Наслідок 2.7.5. Нехай – деяке скінчене бінарне відношення і – деякий порядок на . Тоді виконується співвідношення . Якщо ж автомат скінчений, то .

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

Зокрема, коли і скінчені, повністю визначені, ініціальні та ініціально-зв’язні, теорема 2.7 дає розвязок проблеми ізоморфізма для них, що часто є більш простим від розвязка для загального випадку неініціальних автоматів, який був запропонований Ю.І.Соркіним. Сформулюємо цей розвязок у вигляді наступного твердження.

Наслідок 2.7.6. Нехай і – скінчені системи визначальних співвідношень для автоматів і відповідно. Автомати і s-ізоморфні тоді і лише тоді, коли для будь-якого лінійного порядку .

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

Скінчена множина слів в алфавиті називається обходом (графа) автомата , якщо для будь-яких і існує таке слово , що , та слово є початковим відрізком деякого слова .

За обходом і базисом досяжності визначимо відношення , де , , і – множина початкових відрізків всіх слів з .

Теорема 2.8. Для будь-якого обхода автомата і будь-якого його базиса досяжності відношення є системою визначальних співвідношень для .

Теорема 2.11. Для будь-якої скінченої системи визначальних співвідношень для скінченого, повністю визначеного автомата множина є обходом цього автомата, де – множина початкових відрізків всіх слів з .

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

Введемо відображення і :

Нехай , – множина всіх початкових відрізків обхода , найкоротший за порядком внутрішній базис досяжності автомата відносно . Позначимо

.

Видалимо з всі пари типу . Одержане таким чином відношення позначимо через . Покладемо .

Нехай . Видалимо з всі слова, що є початковими відрізками інших слів з . Одержану таким чином множину позначимо через . Покладемо .

Теорема 2.12. є ін’єкцією, є сюр’єкцією, причому для будь-якого ненадлишкового обхода .

Показано, що у загальному випадку відображення , де . Також показано, що канонічна система визначальних співвідношень є нерухомою точкою відображення .

Теорема 2.13. Для будь-якої канонічної системи визначальних співвідношень виконується рівність .

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

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

Позначимо через множину всіх таких слів , для яких визначена і . Через позначимо множину мінімальних за начальними відрізками слів з . Розширимо

праву конгруенцію до правої конгруенції на множині . Нехай

конкатенація і . Показано (лема 3.1), що .

Повністю визначений автомат називається вільним розширенням скінченого часткового автомата, якщо одночасно виконуються такі умови:

а) для будь-якого ;

б) для будь-якого підавтомат є вільним.

Нехай і – детерміновані скінчені ініціально-зв’язні часткові автомати. Нехай , якщо . З випливає, що . Такі автомати назвемо подібними (по вільному розширенню). Клас усіх автоматів, які є подібними автомату позначимо через . Показано, що автомати є подібними, якщо їхні спеціальні підавтомати, які названо ядрами, є ізоморфними між собою. Знайдено критерий, за яким стан автомата належить його ядру (теорема 3.2).

Пару , де – бінарне відношення на , а назвемо системою. Систему називаємо скінченою, якщо скінчені обидві її компоненти. Система однозначно визначає автомат , оскільки однозначно визначає і , а однозначно визначає звуження до .

Нехай задана довільна система . Нехай – множина початкових відрізків усіх слів з і – зріз бінарного відношення по . Систему назвемо визначальною для автомата , якщо для неї одночасно виконуються наступні умови:

i) ;

ii) ;

iii) .

Легко бачити, що у випадку, коли повністю визначений, і система є визначальною для , то , а є системою визначальних співвідношень для .

Наступне твердження прояснює значення введення визначальної системи для автомата .

Твердження 3.6. Нехай система задовольняє умовам (i)–(iii) для деякого автомата . Тоді вона однозначно визначає автомат , причому .

Визначимо скінчене бінарне відношення на і скінчену множину на за такими правилами: нехай і спочатку порожні. Для кожних і , якщо і , то пара міститься в . Якщо ж не визначена, то слово міститься в .

Теорема 3.3. є визначальною системою для автомата .

Нехай – деяка скінчена визначальна система для автомата . Через позначимо суму числа пар в і числа слів в . Нехай

,

де підсумовування відбувається за всіх парах і словах відповідно. Значення цих характеристик для канонічної визначальної системи автомата визначено наступним твердженням:

Теорема 3.4. а) ;

б) ,

де ;

в) ,

причому оцінки (б) і (в) є досяжними для всіх и .

Під характеризацією системи розуміємо розвязок наступних задач:

(1) Визначити, чи існує скінчений частковий автомат, для якого система є визначальною.

(2) Визначити, чи є визначальною системою для фіксованого часткового автомата .

У підрозділі 3.2 ці задачі розвязані для скінчених систем . Задачу (2) розвязано за допомогою введеної для цієї мети процедури редукції системи. Ця процедура є модифікацією процедури редукції бінарного відношення, що розглянута в підрозділі 2.2.

Систему назвемо правильною тоді і лише тоді, коли існує частковий, можливо нескінчений, автомат , для якого є визначальною системою. У цьому випадку автомат позначаємо . Охарактеризуємо правильні системи. Систему назвемо сумісною, якщо одночасно виконуються такі умови:

і ,

тобто і не протирічать одне одному.

Теорема 3.5. Система є правильною тоді і лише тоді, коли вона є сумісною.

Знайдемо умови для і , за яких автомат є скінченим. Клас всіх правильних систем, що задають скінчені автомати на множині позначимо через . Охарактеризуємо клас систем . Сумісну систему назвемо визначеною, якщо для кожних , існують такі , для яких виконується хоч одна з умов:

а) ;

б) .

Інакше кажучи, в цьому випадку і доповнюють одне одну так, щоб в автоматі не було жодного нескінченого підавтомата-дерева. При цьому ядро автомата скінчене, оскільки скінчене.

Теорема 3.6. Система належить класу тоді і лише тоді, коли вона визначена.

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

Другу задачу характеризації скінченої системи розвязано за допомогою процедури редукції системи, що є аналогічною до процедури редукції бінарного відношення, в якій операцію 3 введено наступним чином.

Нехай , , . Якщо для деякого , то пару в замінюємо парою . Якщо , то пару в замінюємо парою . Якщо ж , то слово в замінюємо словом .

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

Теорема 3.7. Нехай – деякий довільно зафіксований лінійний порядок на , – деякий скінчений частковий автомат і нехай скінчена система , де і , є визначеною. тоді і лише тоді, коли .

Теорема 3.7 є розповсюдженням теореми 2.7 на часткові автомати. Доведено ряд наслідків з теореми 3.7, які аналогічні наслідкам з теореми 2.7.

ВИСНОВКИ

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

Одержані наступні результати:

· вперше знайдено мінімальну так звану канонічну систему визначальних співвідношень та розглянуто її структуру;

· вперше знайдено критерій, за яким скінчене бінарне відношення є системою визначальних співвідношень для заданого скінченого повністю визначеного автомата;

· показано звязок класу систем визначальних співвідношень для даного автомата з іншими його властивостями (базисами досяжності, обходами); запропоновані процедури переходу від обходу до системи визначальних співвідношень і навпаки;

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

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

Ці результати є новими и завершеними.

Таким чином вперше повністю розвязано проблему характеризації скінчених систем визначальних співвідношень для скінчених ініціальних автоматів.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

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.

АНОТАЦІЇ

Сенченко О.С. Зображення автоматів за допомогою визначальних співвідношень їх поведінки. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики. – Інститут кібернетики імені В.М.Глушкова НАН України, Київ, 2005.

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

Ключові слова: автомат, система визначальних співвідношень, базис досяжності, канонічна система визначальних співвідношень, редукція, обхід, визначальна система, ядро автомата, сумісність систем, визначеність систем.

Сенченко А.С. Представление автоматов определяющими соотношениями их поведения. – Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 – теоретические основы информатики и кибернетики. – Институт кибернетики имени В.М.Глушкова НАН Украины, Киев, 2005.

Диссертационная работа посвящена исследованию структурных и метрических свойств систем определяющих соотношений для всюдуопределенных и частичных конечных инициальных автоматов.

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

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

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

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

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

Найдено решение задач характеризации конечной системы – задачи определения, существует ли конечный частично-определенный автомат, для которого данная система является определяющей и задачи определения, является ли данная система определяющей для фиксированного частично-определенного автомата. Найдены необходимые и достаточные условия (условия совместимости), при которых данная система является определяющей для некоторого, возможно бесконечного, частичного автомата. Найдены необходимые и достаточные условия (условия определенности), при которых данная совместимая система является определяющей для некоторого конечного частичного автомата, что является решением первой задачи характеризации системы. Вторая задача характеризации системы решена с помощью введенной для этой цели процедуры редукции системы к канонической. Эта процедура является обобщением процедуры редукции бинарного отношения, причем последняя является ее собственной частью.

Таким образом впервые полностью решена проблема характеризации конечных систем определяющих соотношений для конечных инициальных автоматов.

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

Senchenko A.S. Automata presentation by means of defining relations of their behaviour. – Manuscript.

Thesis for a candidate’s degree of physics and mathematics by speciality 01.05.01 – theoretical basis of informatics and cybernetics. – V.M. Glushkov institute of cybernetics, National Academy of Science of Ukraine, Kyiv, 2005.

The dissertation is devoted to an investigation of structural and metric properties of copresentation for completely defined and partial finite initial automata. A minimal so-called canonical copresentation is defined and its structure is considered. A reduction procedure reducing any finite copresentation to the canonical. A criterion under which a finite binary relation over the input words be a copresentation of given finite completely defined automaton. It is an isomorphism problem solution for finite initial automata without their construction from given copresentation. A relation between the copresentations and the automata bypasses is obtained. A new notion of copresenting system for partial automata is introduced, which is an generalization of the copresentation for complete automata. A minimal copresenting system is found, and its structure is investigated. It is defined necessary and sufficient conditions under which a system be copresenting for any finite automaton.

Key words: automaton, copresentation, accessibility basis, canonical copresentation, reduction, bypass, automaton kernel, copresenting system.