Search academic texts

Registration Number

0412U003992, Candidate dissertation

Status

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

Date

22-06-2012

popup.evolution

o

Title

Algebras of languages representable by labeled graphs

Author

Prianychnykova Olena Oleksiivna,

popup.head Grunsky Igor Sergeevich
popup.opponent Летичевський Олександр Адольфович
popup.opponent Рисцов Ігор Костянтинович

Description

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

popup.nrat_date

2020-04-04