Алгебра мов, що можуть бути представлені в помічених графах
Електронний архів E-archive DonNTU – (Electronic archive Donetsk National Technical University)
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Алгебра мов, що можуть бути представлені в помічених графах
An Algebra of Languages Representable in Vertex-Labelled Graphs |
|
| Creator |
Пряничникова, О.О.
|
|
| Subject |
граф
аналіз синтез детермінізація мінімізація graph analysis synthesis determinization minimization |
|
| Description |
В останні роки а комп'ютерних науках інтенсивно використовуються скінченні орієнтовані графи з поміченими вершинами. В даній статті ми вводимо алгебру мов, що можуть бути представлені в таких графах, і досліджуємо її властивості. На відміну від алгебри регулярних мов, яка здебільшого використовується для графів з поміченими дугами (скінченних автоматів), запропонована алгебра є зручним засобом для дослідження властивостей мов, що можуть бути представлені в графах з поміченими вершинами. В статті для графів з поміченими вершинами доведено теореми, що є аналогами теореми Кліпі і теореми Майхіла-Нерода для скінченних автоматів. Розроблено методи аналізу та синтезу мов, що можуть бути представлені в графах з поміченими вершинами, способи детермінізації та мінімізації таких графів. Для введеної алгебри запропонована скінченна система аксіом, доведена її повнота.
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. |
|
| Date |
2012-05-08T14:58:56Z
2012-05-08T14:58:56Z 2011 |
|
| Type |
Article
|
|
| Identifier |
Пряничникова О.О. Алгебра мов, що можуть бути представлені в помічених графах // Вісник Київського національного університету імені Тараса Шевченка. Серія «Фізико-математичні науки». – 2011. – №1. – С. 193-198
УДК 519.6 http://ea.donntu.edu.ua/handle/123456789/13268 |
|
| Language |
other
|
|