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

Information × 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 Рисцов Ігор Костянтинович Description Дисертаційну роботу присвячено проблемі розробки і дослідження алгебраїчних засобів для аналізу поведінки позначених графів і синтезу таких графів із заданою поведінкою. Введено нове поняття позначеного графа, що охоплює ряд відомих видів графів, які використовуються в комп'ютерних науках. Запропоновано матричне представлення позначених графів, алгебра успішних шляхів в графах та алгебра матриць, породжена алгеброю шляхів, що дозволяє за матрицями графів будувати матриці їх композицій. Створено алгебри, що дозволяють аналізувати поведінку таких графів. Доведено теорему, яка є узагальненням теореми Кліні-Шютценберже на випадок, коли множина поведінок графів не є півкільцем; знайдено умови за яких множина всіх можливих поведінок позначених графів співпадає з множиною всіх можливих значень термів введеної алгебри. Для окремих випадків позначених графів запропоновано спосіб побудови алгебри, яка має необхідніи властивості. Досліджено основні властивості алгебри мов, що можуть бути представлені у графах з позначеними вершинами, знайдено алгебраїчну й лінгвістичну характеризації мов, що можуть бути представлені регулярними виразами цієї алгебри. Введено поняття детермінованого графа з позначеними вершинами та показано, що класи мов, що можуть бути представлені детермінованими й недетермінованими графами, збігаються. Запропоновано спосіб детермінізації графів. Доведено критерій того, що мова може бути представлена графом з позначеними вершинами. Доведено, що для будь-якої мови, що може бути представлена графом з позначеними вершинами, існує єдиний з точністю до ізоморфізму мінімальний повний детермінований граф, та запропоновано спосіб мінімізації графів. Показано, що алгебра мов, що можуть бути представлені у графах з позначеними вершинами, є вільною алгеброю квазібагатовиду зі скінченним базисом, для цієї алгебри розроблено систему аксіом, яка складається з тотожностей і квазітотожностей, та доведено її повноту. Ключові слова: позначені графи, поведінка графа, мови в алфавіті позначок, алгебри мов. Registration Date 2012-07-10 popup.nrat_date 2020-04-04 / 2026-06-30 Close