Registration Number
0412U003992, Candidate dissertation
Status
к.ф.-м.н.
Date
22-06-2012
popup.evolution
.
Title
Algebras of languages representable by labeled graphs
Author
Prianychnykova Olena Oleksiivna,
popup.head Grunsky Igor Sergeevich
popup.opponent Летичевський Олександр Адольфович
popup.opponent Рисцов Ігор Костянтинович
popup.rada
V.M.Glushkov Institute of Cybernetics of NASU
Description
Дисертаційну роботу присвячено проблемі розробки і дослідження алгебраїчних засобів для аналізу поведінки позначених графів і синтезу таких графів із заданою поведінкою. Введено нове поняття позначеного графа, що охоплює ряд відомих видів графів, які використовуються в комп'ютерних науках. Запропоновано матричне представлення позначених графів, алгебра успішних шляхів в графах та алгебра матриць, породжена алгеброю шляхів, що дозволяє за матрицями графів будувати матриці їх композицій. Створено алгебри, що дозволяють аналізувати поведінку таких графів. Доведено теорему, яка є узагальненням теореми Кліні-Шютценберже на випадок, коли множина поведінок графів не є півкільцем; знайдено умови за яких множина всіх можливих поведінок позначених графів співпадає з множиною всіх можливих значень термів введеної алгебри. Для окремих випадків позначених графів запропоновано спосіб побудови алгебри, яка має необхідніи властивості. Досліджено основні властивості алгебри мов, що можуть бути представлені у графах з позначеними вершинами, знайдено алгебраїчну й лінгвістичну характеризації мов, що можуть бути представлені регулярними виразами цієї алгебри. Введено поняття детермінованого графа з позначеними вершинами та показано, що класи мов, що можуть бути представлені детермінованими й недетермінованими графами, збігаються. Запропоновано спосіб детермінізації графів. Доведено критерій того, що мова може бути представлена графом з позначеними вершинами. Доведено, що для будь-якої мови, що може бути представлена графом з позначеними вершинами, існує єдиний з точністю до ізоморфізму мінімальний повний детермінований граф, та запропоновано спосіб мінімізації графів. Показано, що алгебра мов, що можуть бути представлені у графах з позначеними вершинами, є вільною алгеброю квазібагатовиду зі скінченним базисом, для цієї алгебри розроблено систему аксіом, яка складається з тотожностей і квазітотожностей, та доведено її повноту. Ключові слова: позначені графи, поведінка графа, мови в алфавіті позначок, алгебри мов.
Registration Date
2012-07-10
popup.nrat_date
2020-04-04 / 2026-06-30