Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://ea.donntu.edu.ua:8080/jspui/handle/123456789/13268
Название: Алгебра мов, що можуть бути представлені в помічених графах
Другие названия: An Algebra of Languages Representable in Vertex-Labelled Graphs
Авторы: Пряничникова, О.О.
Ключевые слова: граф
аналіз
синтез
детермінізація
мінімізація
graph
analysis
synthesis
determinization
minimization
Дата публикации: 2011
Библиографическое описание: Пряничникова О.О. Алгебра мов, що можуть бути представлені в помічених графах // Вісник Київського національного університету імені Тараса Шевченка. Серія «Фізико-математичні науки». – 2011. – №1. – С. 193-198
Краткий осмотр (реферат): В останні роки а комп'ютерних науках інтенсивно використовуються скінченні орієнтовані графи з поміченими вершинами. В даній статті ми вводимо алгебру мов, що можуть бути представлені в таких графах, і досліджуємо її властивості. На відміну від алгебри регулярних мов, яка здебільшого використовується для графів з поміченими дугами (скінченних автоматів), запропонована алгебра є зручним засобом для дослідження властивостей мов, що можуть бути представлені в графах з поміченими вершинами. В статті для графів з поміченими вершинами доведено теореми, що є аналогами теореми Кліпі і теореми Майхіла-Нерода для скінченних автоматів. Розроблено методи аналізу та синтезу мов, що можуть бути представлені в графах з поміченими вершинами, способи детермінізації та мінімізації таких графів. Для введеної алгебри запропонована скінченна система аксіом, доведена її повнота.
Recently directed finite vertex-labelled graphs have been successfully applied to the diverse areas of computer science, robotics, etc. In this paper we introduce and study an algebra of languages representable by vertex-labelled graphs. In contrast to Kleene algebra of regular languages, which is mainly used for edge-labelled graphs, it can adequately represent many properties of languages generated by vertex-labelled graphs. We prove an analog of Kleene's theorem establishing equivalence of regular expressions in this algebra and vertex-labelled graphs and an analog of the Myhill-Nerode theorem giving the necessary and sufficient conditions for the languages to be representable by a class of directed vertex-labelled graphs. We give several basic constructions, including methods for obtaining of a regular expression in this algebra from vertex-labelled graph and vice versa, determinization and state minimization of vertex-labelled graphs. A finitary axiomatization for considered algebra is developed and its completeness is proved.
URI (Унифицированный идентификатор ресурса): http://ea.donntu.edu.ua/handle/123456789/13268
Располагается в коллекциях:Наукові публікації у фахових виданнях кафедри програмного забезпечення інтелектуальних систем

Файлы этого ресурса:
Файл Описание РазмерФормат 
vis_K_un-2011(1).pdf4,72 MBAdobe PDFПросмотреть/Открыть


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.