Взаимосвязь алгебр языков, представимых в отмеченных графах
В работе рассмотрены основные особенности алгебры языков, представимых в графах с отмеченными вершинами. Показано, что класс языков, представимых регулярными выражениями этой алгебры, совпадает с классом всех регулярных языков, не содержащих пустого слова. Доказано существование изоморфных подалгебр...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/58493 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Взаимосвязь алгебр языков, представимых в отмеченных графах / Е.А. Пряничникова 
 // Штучний інтелект. — 2010. — № 4. — С. 453-459. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862712985204555776 |
|---|---|
| author | Пряничникова, Е.А. |
| author_facet | Пряничникова, Е.А. |
| citation_txt | Взаимосвязь алгебр языков, представимых в отмеченных графах / Е.А. Пряничникова 
 // Штучний інтелект. — 2010. — № 4. — С. 453-459. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| 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.
|
| first_indexed | 2025-12-07T17:40:50Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-58493 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T17:40:50Z |
| publishDate | 2010 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| 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 |
| spellingShingle | Взаимосвязь алгебр языков, представимых в отмеченных графах Пряничникова, Е.А. Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| title | Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_alt | Взаємозв’язок алгебр мов, що можуть бути представлені в помічених графах Relationships Between Algebras of Languages that can be Represented by Labeled Graphs |
| title_full | Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_fullStr | Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_full_unstemmed | Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_short | Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_sort | взаимосвязь алгебр языков, представимых в отмеченных графах |
| topic | Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| topic_facet | Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/58493 |
| 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 |