Головна сторiнка
eng
Наукова бібліотека ім. М. Максимовича UNDP in Ukraine
Увага! Відтепер можна отримати пластиковий читацький квиток також за адресою:
проспект академіка Глушкова 2, кім. 217.

Подробиці читайте тут.
Список містить (0 документів)
Ваше замовлення (0 книжок)
Перегляд стану та історії замовлень
Допомога

Назад Новий пошук

Опис документа:

Автор: Пряничникова О.О.
Назва: Алгебра мов, що можуть бути представлені в помічених графах
Видавництво: ВПЦ "Київський університет"
Рік:
Сторінок: С. 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 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.



Пошук: заповніть хоча б одне з полів


Шукати серед складових частин документу "Вісник Київського національного університету імені Тараса Шевченка"
Розділ:
Назва:
Будь ласка, пишіть 2-3 слова з назви БЕЗ ЗАКІНЧЕНЬ!
Так імовірніше знайти потрібний документ!
слова не коротші ніж 3 символів, розділені пробілами
Автор:
Будь ласка, пишіть прізвище автора без ініціалів!
не коротше ніж 2 символи
є повний текст
Рік видання:
Видавництво:
з     по  
Види документів:
 Книга  Брошура  Конволют (штучно створена збірка)  Рідкісне видання
 Автореферат  Дисертація
 Журнал  Газета
 Стаття  Складова частина документа
Новий тематичний пошук
       
      
        
Цей сайт створено за спiльною програмою UNDP та
Київського нацiонального унiверситету iменi Тараса Шевченка
проект УКР/99/005

© 2000-2010 yawd, irishka, levsha, alex