Взаимосвязь алгебр языков, представимых в отмеченных графах
В работе рассмотрены основные особенности алгебры языков, представимых в графах с отмеченными вершинами. Показано, что класс языков, представимых регулярными выражениями этой алгебры, совпадает с классом всех регулярных языков, не содержащих пустого слова. Доказано существование изоморфных подалгебр...
Збережено в:
| Опубліковано в: : | Штучний інтелект |
|---|---|
| Дата: | 2010 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/58493 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Взаимосвязь алгебр языков, представимых в отмеченных графах / Е.А. Пряничникова // Штучний інтелект. — 2010. — № 4. — С. 453-459. — Бібліогр.: 10 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-58493 |
|---|---|
| record_format |
dspace |
| spelling |
Пряничникова, Е.А. 2014-03-25T15:20:30Z 2014-03-25T15:20:30Z 2010 Взаимосвязь алгебр языков, представимых в отмеченных графах / Е.А. Пряничникова // Штучний інтелект. — 2010. — № 4. — С. 453-459. — Бібліогр.: 10 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/58493 519.6 В работе рассмотрены основные особенности алгебры языков, представимых в графах с отмеченными вершинами. Показано, что класс языков, представимых регулярными выражениями этой алгебры, совпадает с классом всех регулярных языков, не содержащих пустого слова. Доказано существование изоморфных подалгебр у рассматриваемых алгебр. Получены отображения, позволяющие по регулярным выражениям одной алгебры переходить к регулярным выражениям другой алгебры, представляющим тот же язык. Показано, что алгебра языков, представимых в графах с отмеченными вершинами, не является алгеброй Клини, и между этой алгеброй и алгеброй регулярных языков нет гомоморфизма. У роботі розглянуті основні особливості алгебри мов, що можуть бути представлені в графах з поміченими вершинами. Показано, що клас мов, що можуть бути представлені формулами цієї алгебри, співпадає з класом всіх регулярних мов, що не включають порожнього слова. Отримані відображення, що дозволяють переходити від формул однієї алгебри до формул іншої алгебри зі збереженням мови. Доведено, що алгебра мов, що можуть бути представлені в графах з поміченими вершинами, не є алгеброю Кліні, і між цією алгеброю та алгеброю регулярних мов немає гомоморфізму. In this paper we study an algebra of languages that can be represented by vertex-labeled graphs. We establish some new relationships between this algebra and the algebra of regular languages. It is proved that these studied algebras have isomorphic sub algebras. We show that it is always possible to transform regular expression of Kleene algebra into a regular expression of algebra of languages that can be represented by vertex-labeled graphs without changing its language. It is shown that algebra of languages that can be represented by vertex-labeled graphs is not the Kleene algebra. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Интеллектуальные системы планирования, управления, моделирования и принятия решений Взаимосвязь алгебр языков, представимых в отмеченных графах Взаємозв’язок алгебр мов, що можуть бути представлені в помічених графах Relationships Between Algebras of Languages that can be Represented by Labeled Graphs Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Взаимосвязь алгебр языков, представимых в отмеченных графах |
| spellingShingle |
Взаимосвязь алгебр языков, представимых в отмеченных графах Пряничникова, Е.А. Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| title_short |
Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_full |
Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_fullStr |
Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_full_unstemmed |
Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_sort |
взаимосвязь алгебр языков, представимых в отмеченных графах |
| author |
Пряничникова, Е.А. |
| author_facet |
Пряничникова, Е.А. |
| topic |
Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| topic_facet |
Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| publishDate |
2010 |
| language |
Russian |
| container_title |
Штучний інтелект |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Взаємозв’язок алгебр мов, що можуть бути представлені в помічених графах Relationships Between Algebras of Languages that can be Represented by Labeled Graphs |
| description |
В работе рассмотрены основные особенности алгебры языков, представимых в графах с отмеченными вершинами. Показано, что класс языков, представимых регулярными выражениями этой алгебры, совпадает с классом всех регулярных языков, не содержащих пустого слова. Доказано существование изоморфных подалгебр у рассматриваемых алгебр. Получены отображения, позволяющие по регулярным выражениям одной алгебры переходить к регулярным выражениям другой алгебры, представляющим тот же язык. Показано, что алгебра языков, представимых в графах с отмеченными вершинами, не является алгеброй Клини, и между этой алгеброй и алгеброй регулярных языков нет гомоморфизма.
У роботі розглянуті основні особливості алгебри мов, що можуть бути представлені в графах з поміченими вершинами. Показано, що клас мов, що можуть бути представлені формулами цієї алгебри, співпадає з класом всіх регулярних мов, що не включають порожнього слова. Отримані відображення, що дозволяють переходити від формул однієї алгебри до формул іншої алгебри зі збереженням мови. Доведено, що алгебра мов, що можуть бути представлені в графах з поміченими вершинами, не є алгеброю Кліні, і між цією алгеброю та алгеброю регулярних мов немає гомоморфізму.
In this paper we study an algebra of languages that can be represented by vertex-labeled graphs. We establish some new relationships between this algebra and the algebra of regular languages. It is proved that these studied algebras have isomorphic sub algebras. We show that it is always possible to transform regular expression of Kleene algebra into a regular expression of algebra of languages that can be represented by vertex-labeled graphs without changing its language. It is shown that algebra of languages that can be represented by vertex-labeled graphs is not the Kleene algebra.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/58493 |
| citation_txt |
Взаимосвязь алгебр языков, представимых в отмеченных графах / Е.А. Пряничникова // Штучний інтелект. — 2010. — № 4. — С. 453-459. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT prâničnikovaea vzaimosvâzʹalgebrâzykovpredstavimyhvotmečennyhgrafah AT prâničnikovaea vzaêmozvâzokalgebrmovŝomožutʹbutipredstavlenívpomíčenihgrafah AT prâničnikovaea relationshipsbetweenalgebrasoflanguagesthatcanberepresentedbylabeledgraphs |
| first_indexed |
2025-12-07T17:40:50Z |
| last_indexed |
2025-12-07T17:40:50Z |
| _version_ |
1850872168639889408 |