Please use this identifier to cite or link to this item: http://ea.donntu.edu.ua:8080/jspui/handle/123456789/13268
Title: Алгебра мов, що можуть бути представлені в помічених графах
Other Titles: An Algebra of Languages Representable in Vertex-Labelled Graphs
Authors: Пряничникова, О.О.
Keywords: граф
аналіз
синтез
детермінізація
мінімізація
graph
analysis
synthesis
determinization
minimization
Issue Date: 2011
Citation: Пряничникова О.О. Алгебра мов, що можуть бути представлені в помічених графах // Вісник Київського національного університету імені Тараса Шевченка. Серія «Фізико-математичні науки». – 2011. – №1. – С. 193-198
Abstract: В останні роки а комп'ютерних науках інтенсивно використовуються скінченні орієнтовані графи з поміченими вершинами. В даній статті ми вводимо алгебру мов, що можуть бути представлені в таких графах, і досліджуємо її властивості. На відміну від алгебри регулярних мов, яка здебільшого використовується для графів з поміченими дугами (скінченних автоматів), запропонована алгебра є зручним засобом для дослідження властивостей мов, що можуть бути представлені в графах з поміченими вершинами. В статті для графів з поміченими вершинами доведено теореми, що є аналогами теореми Кліпі і теореми Майхіла-Нерода для скінченних автоматів. Розроблено методи аналізу та синтезу мов, що можуть бути представлені в графах з поміченими вершинами, способи детермінізації та мінімізації таких графів. Для введеної алгебри запропонована скінченна система аксіом, доведена її повнота.
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
Appears in Collections:Наукові публікації у фахових виданнях кафедри програмного забезпечення інтелектуальних систем

Files in This Item:
File Description SizeFormat 
vis_K_un-2011(1).pdf4,72 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.