Кандидатська дисертація. Пряничникова Олена Олексіївна. Алгебри мов, що можуть бути представлені в позначених графах

Інформація × Реєстраційний номер 0412U003992, Кандидатська дисертація На здобуття к.ф.-м.н. Дата захисту 22-06-2012 Статус Захищена Назва роботи Алгебри мов, що можуть бути представлені в позначених графах Здобувач Пряничникова Олена Олексіївна, Керівник Грунський Ігор Сергійович Опонент Летичевський Олександр Адольфович Опонент Рисцов Ігор Костянтинович Опис Дисертаційну роботу присвячено проблемі розробки і дослідження алгебраїчних засобів для аналізу поведінки позначених графів і синтезу таких графів із заданою поведінкою. Введено нове поняття позначеного графа, що охоплює ряд відомих видів графів, які використовуються в комп'ютерних науках. Запропоновано матричне представлення позначених графів, алгебра успішних шляхів в графах та алгебра матриць, породжена алгеброю шляхів, що дозволяє за матрицями графів будувати матриці їх композицій. Створено алгебри, що дозволяють аналізувати поведінку таких графів. Доведено теорему, яка є узагальненням теореми Кліні-Шютценберже на випадок, коли множина поведінок графів не є півкільцем; знайдено умови за яких множина всіх можливих поведінок позначених графів співпадає з множиною всіх можливих значень термів введеної алгебри. Для окремих випадків позначених графів запропоновано спосіб побудови алгебри, яка має необхідніи властивості. Досліджено основні властивості алгебри мов, що можуть бути представлені у графах з позначеними вершинами, знайдено алгебраїчну й лінгвістичну характеризації мов, що можуть бути представлені регулярними виразами цієї алгебри. Введено поняття детермінованого графа з позначеними вершинами та показано, що класи мов, що можуть бути представлені детермінованими й недетермінованими графами, збігаються. Запропоновано спосіб детермінізації графів. Доведено критерій того, що мова може бути представлена графом з позначеними вершинами. Доведено, що для будь-якої мови, що може бути представлена графом з позначеними вершинами, існує єдиний з точністю до ізоморфізму мінімальний повний детермінований граф, та запропоновано спосіб мінімізації графів. Показано, що алгебра мов, що можуть бути представлені у графах з позначеними вершинами, є вільною алгеброю квазібагатовиду зі скінченним базисом, для цієї алгебри розроблено систему аксіом, яка складається з тотожностей і квазітотожностей, та доведено її повноту. Ключові слова: позначені графи, поведінка графа, мови в алфавіті позначок, алгебри мов. Дата реєстрації 2012-07-10 Додано/оновлено в НРАТ 2020-04-04 / 2026-06-30 Закрити