Взаимосвязь алгебр языков, представимых в отмеченных графах
В работе рассмотрены основные особенности алгебры языков, представимых в графах с отмеченными вершинами. Показано, что класс языков, представимых регулярными выражениями этой алгебры, совпадает с классом всех регулярных языков, не содержащих пустого слова. Доказано существование изоморфных подалгебр...
Збережено в:
| Дата: | 2010 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2010
|
| Назва видання: | Штучний інтелект |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.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 |
irk-123456789-58493 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-584932014-03-26T03:01:24Z Взаимосвязь алгебр языков, представимых в отмеченных графах Пряничникова, Е.А. Интеллектуальные системы планирования, управления, моделирования и принятия решений В работе рассмотрены основные особенности алгебры языков, представимых в графах с отмеченными вершинами. Показано, что класс языков, представимых регулярными выражениями этой алгебры, совпадает с классом всех регулярных языков, не содержащих пустого слова. Доказано существование изоморфных подалгебр у рассматриваемых алгебр. Получены отображения, позволяющие по регулярным выражениям одной алгебры переходить к регулярным выражениям другой алгебры, представляющим тот же язык. Показано, что алгебра языков, представимых в графах с отмеченными вершинами, не является алгеброй Клини, и между этой алгеброй и алгеброй регулярных языков нет гомоморфизма. У роботі розглянуті основні особливості алгебри мов, що можуть бути представлені в графах з поміченими вершинами. Показано, що клас мов, що можуть бути представлені формулами цієї алгебри, співпадає з класом всіх регулярних мов, що не включають порожнього слова. Отримані відображення, що дозволяють переходити від формул однієї алгебри до формул іншої алгебри зі збереженням мови. Доведено, що алгебра мов, що можуть бути представлені в графах з поміченими вершинами, не є алгеброю Кліні, і між цією алгеброю та алгеброю регулярних мов немає гомоморфізму. 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. 2010 Article Взаимосвязь алгебр языков, представимых в отмеченных графах / Е.А. Пряничникова // Штучний інтелект. — 2010. — № 4. — С. 453-459. — Бібліогр.: 10 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/58493 519.6 ru Штучний інтелект Інститут проблем штучного інтелекту МОН України та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Интеллектуальные системы планирования, управления, моделирования и принятия решений Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| spellingShingle |
Интеллектуальные системы планирования, управления, моделирования и принятия решений Интеллектуальные системы планирования, управления, моделирования и принятия решений Пряничникова, Е.А. Взаимосвязь алгебр языков, представимых в отмеченных графах Штучний інтелект |
| description |
В работе рассмотрены основные особенности алгебры языков, представимых в графах с отмеченными вершинами. Показано, что класс языков, представимых регулярными выражениями этой алгебры, совпадает с классом всех регулярных языков, не содержащих пустого слова. Доказано существование изоморфных подалгебр у рассматриваемых алгебр. Получены отображения, позволяющие по регулярным выражениям одной алгебры переходить к регулярным выражениям другой алгебры, представляющим тот же язык. Показано, что алгебра языков, представимых в графах с отмеченными вершинами, не является алгеброй Клини, и между этой алгеброй и алгеброй регулярных языков нет гомоморфизма. |
| format |
Article |
| author |
Пряничникова, Е.А. |
| author_facet |
Пряничникова, Е.А. |
| author_sort |
Пряничникова, Е.А. |
| title |
Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_short |
Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_full |
Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_fullStr |
Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_full_unstemmed |
Взаимосвязь алгебр языков, представимых в отмеченных графах |
| title_sort |
взаимосвязь алгебр языков, представимых в отмеченных графах |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| publishDate |
2010 |
| topic_facet |
Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/58493 |
| citation_txt |
Взаимосвязь алгебр языков, представимых в отмеченных графах / Е.А. Пряничникова
// Штучний інтелект. — 2010. — № 4. — С. 453-459. — Бібліогр.: 10 назв. — рос. |
| series |
Штучний інтелект |
| work_keys_str_mv |
AT prâničnikovaea vzaimosvâzʹalgebrâzykovpredstavimyhvotmečennyhgrafah |
| first_indexed |
2023-10-18T18:32:17Z |
| last_indexed |
2023-10-18T18:32:17Z |
| _version_ |
1796144479918358528 |