В останні роки в комп"ютерних науках інтенсивно використовуються скінченні орієнтовані графи з поміченими вершинами. В даній статті ми вводимо алгебру мов, що можуть бути представлені в таких графах, і досліджуємо її властивості. На відміну від алгебри регулярних мов, яка здебільшого використовується для графів з поміченими дугами (скінченних автоматів), запропонована алгебра є зручним засобом для дослідження властивостей мов, що можуть бути представлені в графах з поміченими вершинами. В статті для графів з поміченими вершинами доведено теореми, що є аналогами теореми Кліні і теореми Майхіла-Нерода для скінченних автоматів. Розроблено методи аналізу та синтезу мов, що можуть бути представлені в графах з поміченими вершинами, способи детермінізації тамінімізації таких графів. Для введеної алгебри запропонована скінченна система аксіом, доведена її повнота.
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 represenlable 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 g&enerated 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 condi&tions for the languages to be representdble 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, determi&nization and state minimization of vertex-labelled graphs. A finitary axiomatization for considered algebra is developed and its completeness is proved.
З 31.12.2014 по 01.03.2015 Наукова бібліотека читачів не обслуговує.
