Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции
Предлагается новый алгоритм анализа языков, порожденных графами с помеченными вершинами и дугами. Он позволяет находить алгебраическое выражение (в терминах соответствующей алгебры) таких языков. Алгоритм основан на локальной редукции графа, т.е. на последовательном исключении его вершин и дуг. Пред...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2012
|
| Назва видання: | Штучний інтелект |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/57193 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции / Н.В. Ногина, И.С. Грунский // Штучний інтелект. — 2012. — № 3. — С. 348-353. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-57193 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-571932014-03-05T03:01:38Z Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции Ногина, Н.В. Грунский, И.С. Интеллектуальные робототехнические системы Предлагается новый алгоритм анализа языков, порожденных графами с помеченными вершинами и дугами. Он позволяет находить алгебраическое выражение (в терминах соответствующей алгебры) таких языков. Алгоритм основан на локальной редукции графа, т.е. на последовательном исключении его вершин и дуг. Предложен порядок редукции, при котором исключение вершин проводится от финальной к начальной, а также упрощение графа в процессе редукции, что зачастую позволяет уменьшить объем вычислений. Запропоновано новий алгоритм аналізу мов, породжених графами з поміченими вершинами і дугами. Він дозволяє знаходити алгебраїчний вираз (в термінах відповідної алгебри) таких мов. Алгоритм засновано на локальній редукції графа, тобто на послідовному виключенні його вершин та дуг. Запропоновано порядок редукції, при якому видалення вершин проводиться від фінальної до початкової, а також спрощення графа в процесі редукції, що часто дозволяє зменшити обсяг обчислень. New algorithm for analysis of languages generated by graphs with labeled vertices and transitions is proposed. It gives regular expression (in terms of the proper algebra) describing the language. The algorithm is based on a local reduction of the graph, that is the sequential exclusion of vertices and transitions. It is proposed a reduction procedure, in which removal starting at the final vertex to initial, and a simplification of the graph in the process of reduction, which often reduces the amount of computations. 2012 2012 Article Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции / Н.В. Ногина, И.С. Грунский // Штучний інтелект. — 2012. — № 3. — С. 348-353. — Бібліогр.: 8 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/57193 519.713 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 |
2012 |
| topic_facet |
Интеллектуальные робототехнические системы |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/57193 |
| citation_txt |
Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции / Н.В. Ногина, И.С. Грунский // Штучний інтелект. — 2012. — № 3. — С. 348-353. — Бібліогр.: 8 назв. — рос. |
| series |
Штучний інтелект |
| work_keys_str_mv |
AT noginanv sintezregulârnogovyraženiââzykaporoždennogopomečennymgrafommetodomegolokalʹnojredukcii AT grunskijis sintezregulârnogovyraženiââzykaporoždennogopomečennymgrafommetodomegolokalʹnojredukcii |
| first_indexed |
2023-10-18T18:29:21Z |
| last_indexed |
2023-10-18T18:29:21Z |
| _version_ |
1796144348547514368 |